<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="zh-Hans">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">






  
  
  <link rel="stylesheet" media="all" href="/lib/Han/dist/han.min.css?v=3.3">




<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/images/favicon.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon.png?v=5.1.4">


  <link rel="mask-icon" href="/images/favicon.png?v=5.1.4" color="#222">





  <meta name="keywords" content="面试题目," />





  <link rel="alternate" href="/atom.xml" title="平步青云win" type="application/atom+xml" />






<meta name="description" content="LeetCode刷起来！">
<meta name="keywords" content="面试题目">
<meta property="og:type" content="article">
<meta property="og:title" content="LeetCode算法题目C++">
<meta property="og:url" content="https://zxpgo.github.io/2019/06/22/LeetCode算法题目C++/index.html">
<meta property="og:site_name" content="平步青云win">
<meta property="og:description" content="LeetCode刷起来！">
<meta property="og:locale" content="zh-Hans">
<meta property="og:image" content="https://i.imgur.com/9nP8tQc.png">
<meta property="og:image" content="https://i.imgur.com/ZNaZYaP.png">
<meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/0/0d/PascalTriangleAnimated2.gif">
<meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/0/0d/PascalTriangleAnimated2.gif">
<meta property="og:image" content="https://pic.leetcode-cn.com/d447f96d20d1cfded20a5d08993b3658ed08e295ecc9aea300ad5e3f4466e0fe-file_1555699515174">
<meta property="og:image" content="https://i.imgur.com/C3QPVWZ.png">
<meta property="og:image" content="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/binarysearchtree_improved.png">
<meta property="og:updated_time" content="2019-06-20T14:38:21.071Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="LeetCode算法题目C++">
<meta name="twitter:description" content="LeetCode刷起来！">
<meta name="twitter:image" content="https://i.imgur.com/9nP8tQc.png">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"right","display":"post","offset":10,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: 'PAO8LM7QB1',
      apiKey: '',
      indexName: 'Blog',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="https://zxpgo.github.io/2019/06/22/LeetCode算法题目C++/"/>





  <title>LeetCode算法题目C++ | 平步青云win</title>
  





  <script type="text/javascript">
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?7a4517a3ce6d7c50203655d056f01ac3";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>




</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-right page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">平步青云win</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <h1 class="site-subtitle" itemprop="description"></h1>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br />
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            归档
          </a>
        </li>
      
        
        <li class="menu-item menu-item-随笔">
          <a href="/sui" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-question-circle"></i> <br />
            
            随笔
          </a>
        </li>
      

      
        <li class="menu-item menu-item-search">
          
            <a href="javascript:;" class="popup-trigger">
			
          
            
              <i class="menu-item-icon fa fa-search fa-fw"></i> <br />
            
            搜索
          </a>
        </li>
      
    </ul>
  

  
    <div class="site-search">
      
  <div class="popup search-popup local-search-popup">
  <div class="local-search-header clearfix">
    <span class="search-icon">
      <i class="fa fa-search"></i>
    </span>
    <span class="popup-btn-close">
      <i class="fa fa-times-circle"></i>
    </span>
    <div class="local-search-input-wrapper">
      <input autocomplete="off"
             placeholder="搜索..." spellcheck="false"
             type="text" id="local-search-input">
    </div>
  </div>
  <div id="local-search-result"></div>
</div>



    </div>
  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="https://zxpgo.github.io/2019/06/22/LeetCode算法题目C++/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="zxp">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="平步青云win">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">LeetCode算法题目C++</h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2019-06-22T22:28:50+08:00">
                2019-06-22
              </time>
            

            

            
          </span>

          

          
            
          

          
          
             <span id="/2019/06/22/LeetCode算法题目C++/" class="leancloud_visitors" data-flag-title="LeetCode算法题目C++">
               <span class="post-meta-divider">|</span>
               <span class="post-meta-item-icon">
                 <i class="fa fa-eye"></i>
               </span>
               
                 <span class="post-meta-item-text">阅读次数&#58;</span>
               
                 <span class="leancloud-visitors-count"></span>
             </span>
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        <p>LeetCode刷起来！<a id="more"></a></p>
<h3 id="7-整数反转"><a href="#7-整数反转" class="headerlink" title="7. 整数反转"></a>7. 整数反转</h3><p>给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。</p>
<p>示例 1:</p>
<pre><code>输入: 123
输出: 321
</code></pre><p> 示例 2:</p>
<pre><code>输入: -123
输出: -321
</code></pre><p>示例 3:</p>
<pre><code>输入: 120
输出: 21
</code></pre><p>注意:</p>
<p>假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31,  2^31 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0</p>
<p><strong>思路：</strong>每次取整数的最后一位，将整数除以10，一直循环得到整数为0。其中需要注意，整数翻转的时候可能超出了整数的表示范围（-2^32,2^32-1），所以乘以10之前需要判断乘以10之前会不会超过表示范围。</p>
<p>代码：</p>
<pre><code>int reverse(int x) {
        int ans = 0;
        while(x)
        {
            if (ans &gt; INT_MAX/10 || ans &lt; INT_MIN/10)
                return 0;
            ans = (x % 10) + ans * 10;
            x = x /10;
        }
        return ans;
    }
</code></pre><h3 id="9-回文数"><a href="#9-回文数" class="headerlink" title="9. 回文数"></a>9. 回文数</h3><p>判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。</p>
<p>示例 1:</p>
<pre><code>输入: 121
输出: true
</code></pre><p>示例 2:</p>
<pre><code>输入: -121
输出: false
</code></pre><p>解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。<br>示例 3:</p>
<pre><code>输入: 10
输出: false
</code></pre><p>解释: 从右向左读, 为 01 。因此它不是一个回文数。<br>进阶:</p>
<p>你能不将整数转为字符串来解决这个问题吗？</p>
<p><strong>思路：</strong>首先判断整数是否为正数，如果负数则直接返回false，如果x等于0直接返回true。然后就是将将x一位一位放入容器vector中。最后两个指针一个从头开始一个从尾开始，如果两个相等，则同时加加，如果不相等直接返回false。</p>
<p>代码：</p>
<pre><code>bool isPalindrome(int x) {
        vector&lt;int&gt; vi;
        if (x &lt; 0 )
            return false;
        else if (x == 0)
            return true;
        else
        {

            while (x)
            {
                vi.push_back(x%10);
                x = x /10;
            }
        }
        auto ite_begin = vi.begin();
        auto ite_end = vi.end()-1;
        while (ite_begin &lt; ite_end)
        {
            if (*ite_begin == *ite_end)
            {
                ite_begin++;
                ite_end--;
            }
            else
            {
                return false;
            }
        }
        return true;       
    }
</code></pre><h3 id="13-罗马数字转整数"><a href="#13-罗马数字转整数" class="headerlink" title="13. 罗马数字转整数"></a>13. 罗马数字转整数</h3><p>罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。</p>
<pre><code>字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
</code></pre><p>例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。</p>
<p>通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：</p>
<p>I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。<br>X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。<br>C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。<br>给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。</p>
<p>示例 1:</p>
<pre><code>输入: &quot;III&quot;
输出: 3
</code></pre><p>示例 2:</p>
<pre><code>输入: &quot;IV&quot;
输出: 4
</code></pre><p>示例 3:</p>
<pre><code>输入: &quot;IX&quot;
输出: 9
</code></pre><p>示例 4:</p>
<pre><code>输入: &quot;LVIII&quot;
输出: 58
解释: L = 50, V= 5, III = 3.
</code></pre><p>示例 5:</p>
<pre><code>输入: &quot;MCMXCIV&quot;
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
</code></pre><p><strong>思路：</strong>这个题目写得有些复杂，其实挺简单的。题目意思是：小数在大数左侧，则小数变成相应的负数。即<code>IXLDI</code>，结果可以表示为<code>-1-10-50+500+1</code>。</p>
<p>代码：</p>
<pre><code>int romanToInt(string s) {
        map&lt;char, int&gt; cim;
        cim[&apos;I&apos;] = 1;
        cim[&apos;V&apos;] = 5;
        cim[&apos;X&apos;] = 10;
        cim[&apos;L&apos;] = 50;
        cim[&apos;C&apos;] = 100;
        cim[&apos;D&apos;] = 500;
        cim[&apos;M&apos;] = 1000;
        int ans = 0;
        for (int i = 0; i &lt; s.size(); i++)
        {
            if (i &lt; s.size()-1 &amp;&amp; cim[s[i]] &lt; cim[s[i+1]])
                ans -= cim[s[i]];
            else
                ans += cim[s[i]];
        }
        return ans;
    }
</code></pre><h3 id="14-最长公共前缀"><a href="#14-最长公共前缀" class="headerlink" title="14. 最长公共前缀"></a>14. 最长公共前缀</h3><p>编写一个函数来查找字符串数组中的最长公共前缀。</p>
<p>如果不存在公共前缀，返回空字符串 “”。</p>
<p>示例 1:</p>
<pre><code>输入: [&quot;flower&quot;,&quot;flow&quot;,&quot;flight&quot;]
输出: &quot;fl&quot;
</code></pre><p>示例 2:</p>
<pre><code>输入: [&quot;dog&quot;,&quot;racecar&quot;,&quot;car&quot;]
输出: &quot;&quot;
解释: 输入不存在公共前缀。
</code></pre><p>说明:</p>
<p>所有输入只包含小写字母 a-z</p>
<p><strong>思路：</strong>首先确定所有字符串中最短字符串的长度，所有字符串比较的次数就是最短字符串的长度。然后就是针对第一个字符，每次字符串都比较一次，依次比较，如果相等，将当前字符添加到str（用来存储最终的结果），遇到一个不相等，直接break当前循环，返回str。</p>
<p>注意，在C++中string，不能用str[i]往里面填加字符，而应该采用追加的形式，即<code>str += &#39;s&#39;</code>。</p>
<p>代码：</p>
<pre><code>string longestCommonPrefix(vector&lt;string&gt;&amp; strs) {
        int len = INT_MAX;
        string str = &quot;&quot;;
        if (strs.size() &lt; 1)
            return &quot;&quot;;
        for (int i = 0; i &lt; strs.size(); i++)
        {
            len = min(len, (int)strs[i].size());
        }
        int j = 0;
        while (j &lt; len)
        {
            int i = 0;
            while ((i &lt; strs.size()-1) &amp;&amp; (strs[i][j] == strs[i+1][j]) )
                i++;   
            if (i == strs.size()-1)
               str += strs[0][j];
            else
                break;
            j++;
        }
        return str;
    }
</code></pre><h3 id="20-有效的括号"><a href="#20-有效的括号" class="headerlink" title="20. 有效的括号"></a>20. 有效的括号</h3><p>给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。</p>
<p>有效字符串需满足：</p>
<p>左括号必须用相同类型的右括号闭合。<br>左括号必须以正确的顺序闭合。<br>注意空字符串可被认为是有效字符串。</p>
<p>示例 1:</p>
<pre><code>输入: &quot;()&quot;
输出: true
</code></pre><p>示例 2:</p>
<pre><code>输入: &quot;()[]{}&quot;
输出: true
</code></pre><p>示例 3:</p>
<pre><code>输入: &quot;(]&quot;
输出: false
</code></pre><p>示例 4:</p>
<pre><code>输入: &quot;([)]&quot;
输出: false
</code></pre><p>示例 5:</p>
<pre><code>输入: &quot;{[]}&quot;
输出: true
</code></pre><p>思路： 如果遇到([{，就放入栈中，如果遇到)]}，首先判断栈是否为空，如果不为空，然后从栈中弹出元素，看是否能够组成一对，如果没法组成一对，直接返回false。</p>
<p>还有另一种方法，就如遇到(，就将)入栈；如果遇到[，就将]入栈；果遇到{就将}入栈。然后遇到([{就从栈中弹出元素，判断跟当前元素是否相等。</p>
<p>代码：</p>
<pre><code>bool isValid(string s) {
    stack&lt;char&gt; sc;
    if (s.size() == 1)
        return false;
    if (s.size() == 0)
        return true;
    int i = 0;
    while (s[i] != &apos;\0&apos;)
    {
        if (s[i] == &apos;(&apos; || s[i] == &apos;{&apos; || s[i] == &apos;[&apos;)
        {
            sc.push(s[i]);
            i++;
        }
        else if (!sc.empty() &amp;&amp; ((sc.top() == &apos;(&apos; &amp;&amp; s[i] == &apos;)&apos;) || (sc.top() == &apos;[&apos; &amp;&amp; s[i] == &apos;]&apos;) || (sc.top() == &apos;{&apos; &amp;&amp; s[i] == &apos;}&apos;) ))
        {
            sc.pop();
            i++;
        }
        else
        {
            return false;
        }
    }
    if (sc.empty())
        return true;
    return false;
}
</code></pre><h3 id="28-实现strStr"><a href="#28-实现strStr" class="headerlink" title="28. 实现strStr()"></a>28. 实现strStr()</h3><p>实现 strStr() 函数。</p>
<p>给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。</p>
<p>示例 1:</p>
<pre><code>输入: haystack = &quot;hello&quot;, needle = &quot;ll&quot;
输出: 2
</code></pre><p>示例 2:</p>
<pre><code>输入: haystack = &quot;aaaaa&quot;, needle = &quot;bba&quot;
输出: -1
</code></pre><p>说明:</p>
<p>当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。</p>
<p>对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。</p>
<p><strong>思路：</strong></p>
<p>第一种解法：暴力解法。设父字符串为P，子串为L。对L中的字符一个一个在P中对比，如果遇到不想当的，P中的标记向前走一步，L中的标记回到0。直到其他一个字符串到达末尾结束。</p>
<p>第二种解法：KMP，比较复杂，在此不论述，，可以百度一下。</p>
<p>还有就是可以直接调用string的库函数。</p>
<p>代码：</p>
<pre><code>int strStr(string haystack, string needle) {
  /*直接调用string库
  int temp = haystack.find(needle);
    return temp;*/
  int len_hay = haystack.size();
  int len_nee = needle.size();
  if (len_nee == 0)
      return 0;
  if (len_hay == 0)
      return -1;
  int i = 0;
  int j = 0;
  int temp = 1;
  while (needle[j] != &apos;\0&apos; &amp;&amp; haystack[i] != &apos;\0&apos;)
  {
      if(haystack[i++] != needle[j++])
      {
          j = 0;
          i = temp;
          temp += 1;
      }
  }
  if (needle[j] == &apos;\0&apos;)
      return i-needle.size();
  else 
      return -1;
}
</code></pre><h3 id="38-报数"><a href="#38-报数" class="headerlink" title="38. 报数"></a>38. 报数</h3><p>报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：</p>
<pre><code>1.     1
2.     11
3.     21
4.     1211
5.     111221
</code></pre><ul>
<li>1 被读作  “one 1”  (“一个一”) , 即 11。</li>
<li>11 被读作 “two 1s” (“两个一”）, 即 21。</li>
<li>21 被读作 “one 2”,  “one 1” （”一个二” ,  “一个一”) , 即 1211。</li>
</ul>
<p>给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。</p>
<p>注意：整数顺序将表示为一个字符串。</p>
<p>示例 1:</p>
<pre><code>输入: 1
输出: &quot;1&quot;
</code></pre><p>示例 2:</p>
<pre><code>输入: 4     
输出: &quot;1211&quot;
</code></pre><p>思路： 对于每次都判断一下当前字符跟下一个字符是否相等，如果相等则，计数器count加1，否则直接将count转换为字符串加上当前字符一起加到答案字符串的结尾，直到字符串到达结尾结束。</p>
<p>代码：</p>
<pre><code>string countAndSay(int n) {
        string s;
        string str(&quot;1&quot;);
        if (n == 1)
            return  str;
        for (int i = 2; i &lt;= n; i++)
        {
            int j = 0;
            int count = 1;
            string s;
            while(str[j] != &apos;\0&apos;)
            {
                if (str[j] == str[j+1])
                    count++;
                else
                {
                    s +=to_string(count)+str[j]; 
                    count = 1;
                }
                j++;
            }
            str = s;
        }
        return str;
    }
</code></pre><h3 id="53-最大子序和"><a href="#53-最大子序和" class="headerlink" title="53. 最大子序和"></a>53. 最大子序和</h3><p>给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。</p>
<p>示例:</p>
<pre><code>输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
</code></pre><p>进阶:</p>
<p>如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。</p>
<p><strong>思路：</strong> 这是一道动态规划的问题。边界条件是数组遍历结束，最有子结构是如果前面的序列小于零，则对于最大和不会起到作用，所以直接加0，如果前面的序列最大和大于0，则表示前面的序列对最大和会起作用，将前面序列的最大和加到当前序列的最大和。</p>
<p>代码：</p>
<pre><code>int maxSubArray(vector&lt;int&gt;&amp; nums) {
       int n = nums.size();
       int * dp = new int[n];
       dp[0] = nums[0];
       int m = nums[0];
       for (int i = 1; i &lt; n; i++)
       {
           dp[i] = nums[i] + (dp[i-1] &gt; 0 ?  dp[i-1] : 0);
           m = max(m, dp[i]);
       }
       return m;
   }
</code></pre><h3 id="58-最后一个单词的长度"><a href="#58-最后一个单词的长度" class="headerlink" title="58. 最后一个单词的长度"></a>58. 最后一个单词的长度</h3><p>给定一个仅包含大小写字母和空格 ‘ ‘ 的字符串，返回其最后一个单词的长度。</p>
<p>如果不存在最后一个单词，请返回 0 。</p>
<p>说明：一个单词是指由字母组成，但不包含任何空格的字符串。</p>
<p>示例:</p>
<pre><code>输入: &quot;Hello World&quot;
输出: 5
</code></pre><p><strong>思路：</strong>如果字符串的末尾有空格，则将字符串的长度减去空格的数量。然后但遇到最后一个字符串前面的空格就结束，并记录该空格的位置。最后，将字符串长度减去空格的位置移动，就得到最后一个单词的长度。</p>
<p>代码：</p>
<pre><code>int lengthOfLastWord(string s) {
    int len = s.size();
    if (len == 0 || (len == 1 &amp;&amp; s[0] == &apos; &apos;))
        return 0;
    int i;
    while (s[len-1] == &apos; &apos; )
    {
        len--;
    }
    for (i = len - 1;  i &gt;= 0 ; i--)
    {

        if (s[i] == &apos; &apos;)
        {
            break;
        }
    }
    return len-i-1;
}
</code></pre><h3 id="66-加一"><a href="#66-加一" class="headerlink" title="66. 加一"></a>66. 加一</h3><p>给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。</p>
<p>最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。</p>
<p>你可以假设除了整数 0 之外，这个整数不会以零开头。</p>
<p>示例 1:</p>
<pre><code>输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
</code></pre><p>示例 2:</p>
<pre><code>输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。
</code></pre><p><strong>思路：</strong> 将最后一个数字加1，并除以10，如果等于0，表示不需要进位，如果等于1，表示需要进位。如果到达数组中的第一个数字，并且有进位，则需要在数组之前添加一个1。</p>
<p>其实这样做有些复杂，可以直接判断数组中的元素是否为9，如果为9表示需要进位，如果不为9则不需要进位。在第一位时，并且该元素为9，则需要在数组之前添加一个1。</p>
<p>代码：</p>
<pre><code>vector&lt;int&gt; plusOne(vector&lt;int&gt;&amp; digits) {
    int i = digits.size()-1;
    int temp = 1;
    while (i &gt;= 0)
    {
        temp = (digits[i]+temp) / 10;
        if (temp == 0)
        {
            digits[i] = (digits[i]+1) % 10;
            break;
        }
        else
        {
            digits[i] = (digits[i]+temp) % 10;
            if (i == 0 &amp;&amp; temp == 1 )
                digits.insert(digits.begin(), 1);
        }
        i--;
    }
    return digits;
}
</code></pre><h3 id="67-二进制求和"><a href="#67-二进制求和" class="headerlink" title="67. 二进制求和"></a>67. 二进制求和</h3><p>给定两个二进制字符串，返回他们的和（用二进制表示）。</p>
<p>输入为非空字符串且只包含数字 1 和 0。</p>
<p>示例 1:</p>
<pre><code>输入: a = &quot;11&quot;, b = &quot;1&quot;
输出: &quot;100&quot;
</code></pre><p>示例 2:</p>
<pre><code>输入: a = &quot;1010&quot;, b = &quot;1011&quot;
输出: &quot;10101&quot;
</code></pre><p><strong>思路：</strong> 首先，判断两个字符串的长度，将最大的字符串放入a。然后执行最大字符串长度次数的循环，如果两个元素加起来等于2，则需要进位，如果不等式2，则不需要进位。</p>
<p>注意，字符串需要转换为整数，即减去48。</p>
<p>代码：</p>
<pre><code>string addBinary(string a, string b) {
    string temp;
    if (a.size() &lt; b.size())
    {
        temp = a;
        a = b;
        b = temp;
    }
    int i = a.size()-1;
    int j = b.size() - 1;
    bool t = 0;
    char k;
    while (i &gt;= 0)
    {
        if (j &gt;=  0)
        {
            k = a[i];
            a[i] = ((a[i] - 48 + b[j]  -48+ t) % 2) + 48;
            t = (k - 48 + b[j] - 48 + t) / 2;
            j--;
        }
        else
        {
            k= a[i];
            a[i] = (a[i] - 48 + t) % 2 + 48;
            t = (k -48+ t) / 2;
        }
        if (i == 0 &amp;&amp; t == 1)
        {
            a.insert(a.begin(), &apos;1&apos;);
        }
        i--;
    }
    return a;
}
</code></pre><h2 id="第二周"><a href="#第二周" class="headerlink" title="第二周"></a>第二周</h2><h3 id="69-x的平方根"><a href="#69-x的平方根" class="headerlink" title="69. x的平方根"></a>69. x的平方根</h3><p>实现 int sqrt(int x) 函数。</p>
<p>计算并返回 x 的平方根，其中 x 是非负整数。</p>
<p>由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。</p>
<p>示例 1:</p>
<pre><code>输入: 4
输出: 2
</code></pre><p>示例 2:</p>
<pre><code>输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。
</code></pre><p><strong>直观的方法：</strong></p>
<p>思路：从1开始一个一个尝试，看是否满足平方根的条件。需要注意的是，不能用乘法，只能用除法，乘法会超过int的表示范围。这样做速度太慢。</p>
<p>代码：</p>
<pre><code>int mySqrt(int x) {
        if (x &lt;= 0)
            return x;
        int i = 1;
        while (i &lt;= x)
        {
            if (i &lt;= x/i &amp;&amp; x/(i+1) &lt; (i+1))
                break;
            i++;
        }
        return i;

    }
</code></pre><p><strong>牛顿迭代法：</strong></p>
<p>思路： 找到一个数r，使得<code>r^2-n=0</code>。即求解该方程。然后利用牛顿迭代法求解该方程。迭代公式：</p>
<pre><code>x=(x+n/x)/2;
</code></pre><p>牛顿迭代的具体公式：</p>
<p><img src="https://i.imgur.com/9nP8tQc.png" alt=""></p>
<p>图曲线图：</p>
<p><img src="https://i.imgur.com/ZNaZYaP.png" alt=""></p>
<p>一直逼近点x*。</p>
<p>代码：</p>
<pre><code>int mySqrt(int x) {
        if (x &lt;= 0)
            return x;
        long r = x;
        while (r &gt; x / r)
            r = (r + x/r) / 2;
        return r;
    }
</code></pre><p>###</p>
<p>假设你正在爬楼梯。需要 n 阶你才能到达楼顶。</p>
<p>每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？</p>
<p>注意：给定 n 是一个正整数。</p>
<p>示例 1：</p>
<pre><code>输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶
</code></pre><p>示例 2：</p>
<pre><code>输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶
</code></pre><p><strong>思路：</strong>这是一个动态规划问题(DP)，边界条件是，只有1阶时，dp[1] = 1; 只有2阶时，dp[2] = 2。最优子结构：向前走一步和或向前走两步，然后将两种情况的相加。</p>
<pre><code>dp[i] = dp[i-1] + dp[i-2];
</code></pre><p>可以使用递归的形式实现。</p>
<p>代码：<br>      int climbStairs(int n) {<br>            if (n == 1)<br>                return 1;</p>
<pre><code>    /*if (n == 1)
        return 1;
    if (n == 2)
        return 2;
    int a = climbStairs(n-1) + climbStairs(n-2);
    return a;*/
    if (n == 1)
        return 1;
    int * dp = new int[n+1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i &lt;= n; i++)
    {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}
</code></pre><h3 id="83-删除排序列表中的重复元素"><a href="#83-删除排序列表中的重复元素" class="headerlink" title="83. 删除排序列表中的重复元素"></a>83. 删除排序列表中的重复元素</h3><p>给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。</p>
<p>示例 1:</p>
<pre><code>输入: 1-&gt;1-&gt;2
输出: 1-&gt;2
</code></pre><p>示例 2:</p>
<pre><code>输入: 1-&gt;1-&gt;2-&gt;3-&gt;3
输出: 1-&gt;2-&gt;3
</code></pre><p><strong>思路：</strong>直接前后两个元素比较，如果相等，则删除第二元素。</p>
<p>代码：</p>
<pre><code>ListNode* deleteDuplicates(ListNode* head) {
    map&lt;int, int&gt; map_i_i;
    ListNode * temp = head;
    ListNode * p = NULL;
    if (temp != NULL &amp;&amp; temp-&gt;next != NULL)
        p = temp-&gt;next;
    while (temp != NULL &amp;&amp;  p != NULL)
    {

        if (temp-&gt;val == p-&gt;val)
        {
            temp-&gt;next = p-&gt;next;
            ListNode * q = p;
            p =  p-&gt;next;
            delete q;
        }
        else
        {
            temp = p;
            p = p-&gt;next;
        }
    }
    return head;
}
</code></pre><h3 id="88-合并两个有序数组"><a href="#88-合并两个有序数组" class="headerlink" title="88. 合并两个有序数组"></a>88. 合并两个有序数组</h3><p>给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。</p>
<p>说明:</p>
<p>初始化 nums1 和 nums2 的元素数量分别为 m 和 n。<br>你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。<br>示例:</p>
<p>输入:<br>    nums1 = [1,2,3,0,0,0], m = 3<br>    nums2 = [2,5,6],       n = 3</p>
<pre><code>输出: [1,2,2,3,5,6]
</code></pre><p><strong>思路：</strong>新创建一个数组，然后另一个数组之间元素相比，小的元素放入新数组。</p>
<p>代码：</p>
<pre><code>void merge(vector&lt;int&gt;&amp; nums1, int m, vector&lt;int&gt;&amp; nums2, int n) {
    int i = 0, j = 0, k = 0;
    vector&lt;int&gt; temp(n+m, 0);
    while (i &lt; m || j &lt; n)
    {
        if (i &gt;= m)
            temp[k++] = nums2[j++];
        else if (j &gt;= n)
            temp[k++] = nums1[i++];
        else if (nums1[i] &gt;= nums2[j])
            temp[k++] = nums2[j++];
        else
            temp[k++] = nums1[i++];
    }
    i = 0;
    k = 0;
    while(i &lt; m+n)
        nums1[i++] = temp[k++];
}
</code></pre><h3 id="1-两数之和"><a href="#1-两数之和" class="headerlink" title="1. 两数之和"></a>1. 两数之和</h3><p>给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。</p>
<p>你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。</p>
<p>示例:</p>
<pre><code>给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
</code></pre><p><strong>思路：</strong> 创建一个字典，将所有元素当作key，其对应的下标当作value，添加的字典map中。然后用target减去每一个元素，判断得到的差在不在map中，如果在map，这返回该值的下标和map中对应差的value。</p>
<p>代码：</p>
<pre><code>vector&lt;int&gt; twoSum(vector&lt;int&gt;&amp; nums, int target) {
    map&lt;int, int&gt; map_i_i;
    for (int i = 0; i &lt; nums.size(); i++)
        map_i_i[nums[i]] = i;
    for (int i = 0; i &lt; nums.size(); i++)
    {
        if (map_i_i.find(target-nums[i]) != map_i_i.end() &amp;&amp; i != map_i_i[target-nums[i]])
            return {i, map_i_i[target-nums[i]]};
    }
    return {};
}
</code></pre><h3 id="26-删除排序数组中的重复项"><a href="#26-删除排序数组中的重复项" class="headerlink" title="26. 删除排序数组中的重复项"></a>26. 删除排序数组中的重复项</h3><p>给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。</p>
<p>不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。</p>
<p>示例 1:</p>
<pre><code>给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。
</code></pre><p>示例 2:</p>
<pre><code>给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。
</code></pre><p>说明:</p>
<p>为什么返回数值是整数，但输出的答案是数组呢?</p>
<p>请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。</p>
<p>你可以想象内部操作如下:</p>
<pre><code>// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i &lt; len; i++) {
    print(nums[i]);
}
</code></pre><p>思路: 定义一个指针从0开始，i从1开始，然后两个元素相等，res不变，i向前走一个；如果两个元素相等，则将nums[i]赋给nums[res++]，相同将i和res向前走一个。</p>
<p>代码：</p>
<pre><code>int removeDuplicates(vector&lt;int&gt;&amp; nums) {
        int res = 0;
        if (nums.size() == 0)
            return 0;
        for (int i = 1; i &lt; nums.size(); i++)
        {
            if (nums[res] != nums[i])
            {
                nums[++res] = nums[i];
            }


        }
        return res+1;
    }
</code></pre><h3 id="27-移除重复元素"><a href="#27-移除重复元素" class="headerlink" title="27. 移除重复元素"></a>27. 移除重复元素</h3><p>给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。</p>
<p>不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。</p>
<p>元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。</p>
<p>示例 1:</p>
<pre><code>给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

你不需要考虑数组中超出新长度后面的元素。
</code></pre><p>示例 2:</p>
<pre><code>给定 nums = [0,1,2,2,3,0,4,2], val = 2,

函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

注意这五个元素可为任意顺序。

你不需要考虑数组中超出新长度后面的元素。
</code></pre><p>说明:</p>
<p>为什么返回数值是整数，但输出的答案是数组呢?</p>
<p>请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。</p>
<p>你可以想象内部操作如下:</p>
<pre><code>// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i &lt; len; i++) {
    print(nums[i]);
}
</code></pre><p>思路：定义一个res指针，指向需要被替换的元素。如果i指向的元素相等val，则res不变，i向下移动一个；如果i指向元素不等于val，则将i指向的元素赋给res位置。</p>
<p>代码：</p>
<pre><code>int removeElement(vector&lt;int&gt;&amp; nums, int val) {
    int i;
    if (nums.size() == 0)
        return 0;
    int res = 0;
    for(i = 0; i &lt; nums.size(); i++)
    {
        if (nums[i] != val)
            nums[res++] = nums[i];
    }
    return res;
}
</code></pre><h3 id="35-搜索插入位置"><a href="#35-搜索插入位置" class="headerlink" title="35. 搜索插入位置"></a>35. 搜索插入位置</h3><p>给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。</p>
<p>你可以假设数组中无重复元素。</p>
<p>示例 1:</p>
<pre><code>输入: [1,3,5,6], 5
输出: 2
</code></pre><p>示例 2:</p>
<pre><code>输入: [1,3,5,6], 2
输出: 1
</code></pre><p>示例 3:</p>
<pre><code>输入: [1,3,5,6], 7
输出: 4
</code></pre><p>示例 4:</p>
<pre><code>输入: [1,3,5,6], 0
输出: 0
</code></pre><p>思路：如果目标元素小于等于数组中的元素，则该元素对应的下标就是i所在值或所需插入的位置。如果目标值比数组中最大元素还有大，则返回数组的长度。</p>
<p>代码：</p>
<pre><code>int searchInsert(vector&lt;int&gt;&amp; nums, int target) {
       int i;
       for (i = 0; i &lt; nums.size(); i++)
           if (nums[i] &gt;= target)
               return i;
       return i;
   }
</code></pre><h3 id="118-杨辉三角"><a href="#118-杨辉三角" class="headerlink" title="118. 杨辉三角"></a>118. 杨辉三角</h3><p>给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。</p>
<p><img src="https://upload.wikimedia.org/wikipedia/commons/0/0d/PascalTriangleAnimated2.gif" alt=""></p>
<p>在杨辉三角中，每个数是它左上方和右上方的数的和。</p>
<p>示例:</p>
<pre><code>输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
</code></pre><p>思路: 略</p>
<p>代码：</p>
<pre><code>vector&lt;vector&lt;int&gt;&gt; generate(int numRows) {
        vector&lt;vector&lt;int&gt;&gt;  ans(numRows);
        for (int i = 0; i &lt; numRows; i++)
        {
            ans[i] = vector&lt;int&gt;(i+1);
            ans[i][0] = ans[i][i] = 1;
            for (int j = 1; j &lt; i; j++)
            {
                ans[i][j] = ans[i-1][j-1] + ans[i-1][j];
            }

        }
        return ans;
    }
</code></pre><h3 id="119-杨辉三角Ⅱ"><a href="#119-杨辉三角Ⅱ" class="headerlink" title="119. 杨辉三角Ⅱ"></a>119. 杨辉三角Ⅱ</h3><p>给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。</p>
<p><img src="https://upload.wikimedia.org/wikipedia/commons/0/0d/PascalTriangleAnimated2.gif" alt=""></p>
<p>在杨辉三角中，每个数是它左上方和右上方的数的和。</p>
<p>示例:</p>
<pre><code>输入: 3
输出: [1,3,3,1]
进阶：
</code></pre><p>你可以优化你的算法到 O(k) 空间复杂度吗？</p>
<p>最简单的做法，但是空间复杂度比较高，无法满足o(k)。</p>
<p>思路：略</p>
<p>代码：</p>
<pre><code>vector&lt;int&gt; getRow(int rowIndex) {
        vector&lt;vector&lt;int&gt;&gt;  ans(rowIndex+1);
            for (int i = 0; i &lt;= rowIndex; i++)
            {
                ans[i] = vector&lt;int&gt;(i+1);
                ans[i][0] = ans[i][i] = 1;
                for (int j = 1; j &lt; i; j++)
                {
                    ans[i][j] = ans[i-1][j-1] + ans[i-1][j];
                }

            }
            return ans[rowIndex];
    }
</code></pre><p>考虑复杂度</p>
<p>思路：利用杨辉三角的推导公式。每一项等于该项所在的行号减1的阶乘除以列号减1的阶乘和行号减列号的阶乘之积。</p>
<p>但是由于阶乘得到的数非常大，甚至超过了long long类型。在求每项的元素，无法每次求出阶乘。可以通过下面的迭代公式求得：</p>
<p>直接使用组合公式C(n,i) = n!/(i!*(n-i)!), 则第(i+1)项是第i项的倍数=(n-i+1)/i;</p>
<p>注意行号n从0开始，列号i从0开始。</p>
<p>代码：</p>
<pre><code>vector&lt;int&gt; getRow(int rowIndex) {
       vector&lt;int&gt;  ans(rowIndex+1);
       ans[0] = ans[rowIndex] = 1;
       long temp = 1;
       for (int i = 1; i &lt;= (rowIndex+1)/2; i++)
       {
          temp = temp * (rowIndex-i+1) / i;
          ans[i] = ans[rowIndex-i] = temp;
       }
       return ans;
   }
</code></pre><h3 id="121-买卖股票的最佳时机-Ⅰ"><a href="#121-买卖股票的最佳时机-Ⅰ" class="headerlink" title="121. 买卖股票的最佳时机 Ⅰ"></a>121. 买卖股票的最佳时机 Ⅰ</h3><p>给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。</p>
<p>如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。</p>
<p>注意你不能在买入股票前卖出股票。</p>
<p>示例 1:</p>
<pre><code>输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
</code></pre><p>示例 2:</p>
<pre><code>输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
</code></pre><p>思路： 这一个求山的峰谷的问题，即求出最低谷到最高峰的差值。首先，将最大利润设置为0，最低谷设置为第一个元素的值。然后每次循环，判断当前元素是否为低谷，最后，将每个元素都与低谷做差，并取最大的差值。</p>
<pre><code>int maxProfit(vector&lt;int&gt;&amp; prices) {
        if (prices.size() &lt;= 1)
            return 0;
        int minprices = prices[0];  
        int maxprofit = 0;
        for (int i = 1; i &lt; prices.size(); i++)
        {

            minprices = min(minprices, prices[i]);
            int profit =  prices[i] - minprices;
            maxprofit = max(profit, maxprofit);
        }
        return maxprofit;
    }
</code></pre><h3 id="122-买卖股票的最佳时机Ⅱ"><a href="#122-买卖股票的最佳时机Ⅱ" class="headerlink" title="122. 买卖股票的最佳时机Ⅱ"></a>122. 买卖股票的最佳时机Ⅱ</h3><p>给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。</p>
<p>设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。</p>
<p>注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。</p>
<p>示例 1:</p>
<pre><code>输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
</code></pre><p>示例 2:</p>
<pre><code>输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
</code></pre><p>示例 3:</p>
<pre><code>输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
</code></pre><p>思路：这也是一个山的峰谷的问题，不过这是求出所有的低谷到山峰差值的和。而上一个题目是求最大的山谷。每过了一个山峰，就将最大利润和最低谷重置，计算下一个峰。</p>
<p><img src="https://pic.leetcode-cn.com/d447f96d20d1cfded20a5d08993b3658ed08e295ecc9aea300ad5e3f4466e0fe-file_1555699515174" alt=""></p>
<p>代码：</p>
<pre><code>int maxProfit(vector&lt;int&gt;&amp; prices) {
    if (prices.size() &lt;= 1)
        return 0;
    int maxprofit = 0;
    int sum = 0;
    int minprice = prices[0];
    for (int i = 1; i &lt; prices.size(); i++)
    {
        minprice = min(minprice, prices[i]);
        maxprofit = max(prices[i] - minprice, maxprofit);
        if (i &lt; prices.size()-1 &amp;&amp; prices[i+1] &lt; prices[i])
        {
            sum += maxprofit;
            maxprofit = 0;
            minprice = prices[i+1];
        }
    }
    sum += maxprofit;
    return sum;
}
</code></pre><h3 id="167-两数之和Ⅱ-输入有序数组"><a href="#167-两数之和Ⅱ-输入有序数组" class="headerlink" title="167. 两数之和Ⅱ-输入有序数组"></a>167. 两数之和Ⅱ-输入有序数组</h3><p>给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。</p>
<p>函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。</p>
<p>说明:</p>
<ul>
<li>返回的下标值（index1 和 index2）不是从零开始的。</li>
<li>你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。</li>
</ul>
<p>示例:</p>
<pre><code>输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
</code></pre><p>思路： 两个指针法。一个指针指i向最开头的元素，另一个指针j指向最末尾的元素。如果两个元素的和等于target，这将这两个值的下标放入数组中。如果最末尾的元素大于target或者两个两个元素的值加起来大于target，则j向前移动；如果两个元素的值加起来小于target，则指针i先后移动。</p>
<p>代码：</p>
<pre><code>vector&lt;int&gt; twoSum(vector&lt;int&gt;&amp; numbers, int target) {
    if (numbers.size() &lt;= 1)
        return {};
    vector&lt;int&gt; res;
    //双指针
    int i = 0; 
    int j = numbers.size()-1;
    while(i &lt; j)
    {
        if (numbers[i] + numbers[j] == target)
        {
            res.push_back(i+1);
            res.push_back(j+1);
            break;
        }
        if(numbers[j] &gt; target || numbers[i] + numbers[j] &gt; target)
            j--;
        if (numbers[i] + numbers[j] &lt; target)
            i++;
    }
    return res;
}
</code></pre><p>暴力解法：</p>
<pre><code>vector&lt;int&gt; twoSum(vector&lt;int&gt;&amp; numbers, int target) {
    if (numbers.size() &lt;= 1)
        return {};
    vector&lt;int&gt; res;
    //暴力解法
    for (int i = 0; i &lt; numbers.size()-1 &amp;&amp; numbers[i] &lt;= target; i++)
    {
        auto t = find(numbers.begin()+i+1, numbers.end(), target - numbers[i]);
        if ( t != numbers.end())
        {
            res.push_back(i+1);
            res.push_back(distance(numbers.begin(), t)+1);
            break;
        }
    }
    return res;
}
</code></pre><h3 id="169-求众数"><a href="#169-求众数" class="headerlink" title="169. 求众数"></a>169. 求众数</h3><p>给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。</p>
<p>你可以假设数组是非空的，并且给定的数组总是存在众数。</p>
<p>示例 1:</p>
<pre><code>输入: [3,2,3]
输出: 3
</code></pre><p>示例 2:</p>
<pre><code>输入: [2,2,1,1,1,2,2]
输出: 2
</code></pre><p>方法一：字典计数法</p>
<p>思路：使用一个字典来记录每个元素出现的次数，key为对应的元素，value为key出现的次数。然后找出value最大所对应的key。</p>
<p>代码：</p>
<pre><code>int majorityElement(vector&lt;int&gt;&amp; nums) {
    map&lt;int, int&gt; map_i_i;
    for (int i = 0; i &lt; nums.size(); i++)
    {
        if (map_i_i.find(nums[i]) != map_i_i.end())
            map_i_i[nums[i]]++;
        else
            map_i_i[nums[i]] = 1;
    }
    int m = 0;
    int temp = 0;
    for (auto ite = map_i_i.begin(); ite != map_i_i.end(); ite++)
    {
        if (ite-&gt;second &gt;= m)
        {
            temp = ite-&gt;first;
            m = ite-&gt;second;
        }

    }
    return temp;
</code></pre><p>方法二：</p>
<p>用一个计数器进行计数。从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，减到0就重新换个数开始计数，总能找到最多的那个</p>
<pre><code>int majorityElement(vector&lt;int&gt;&amp; nums) {
        int count = 1;
        int temp = nums[0];
        for (int i = 1; i &lt; nums.size(); i++)
        {
            if (nums[i] == temp)
                count++;
            else
            {
                count--;
                if (count == 0)
                    temp = nums[i+1];
            }
        }
        return temp;
    }
</code></pre><p>方法三：</p>
<p>先对数组排序，然后取数组的中间元素。</p>
<pre><code>int majorityElement(vector&lt;int&gt;&amp; nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size()/2];
    }
</code></pre><p>方法二的效率最高。</p>
<h3 id="189-旋转数组"><a href="#189-旋转数组" class="headerlink" title="189. 旋转数组"></a>189. 旋转数组</h3><p>给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。</p>
<p>示例 1:</p>
<pre><code>输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
</code></pre><p>示例 2:</p>
<pre><code>输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
</code></pre><p>说明:</p>
<p>尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。<br>要求使用空间复杂度为 O(1) 的原地算法。</p>
<p>思路：将数组旋转三次就可以得到想要的结果。首先，对整体数组旋转一次，其次，对前k个元素旋转一次，最后，对后n-k个元素旋转一次。</p>
<p>代码：</p>
<pre><code>void rotate(vector&lt;int&gt;&amp; nums, int k) {
        if (nums.size() == 1)
            return;
        k = k % nums.size();
        reverse(nums, 0, nums.size()-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, nums.size()-1);
    }


    void reverse(vector&lt;int&gt; &amp; nums, int a, int b)
    {
        int t = 1;
        while (a &lt; b)
        {
            int temp = nums[a];
            nums[a] = nums[b];
            nums[b] = temp;
            a++;
            b--;
        }
    }
</code></pre><h3 id="217-存在重复元素"><a href="#217-存在重复元素" class="headerlink" title="217. 存在重复元素"></a>217. 存在重复元素</h3><p>给定一个整数数组，判断是否存在重复元素。</p>
<p>如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。</p>
<p>示例 1:</p>
<pre><code>输入: [1,2,3,1]
输出: true
</code></pre><p>示例 2:</p>
<pre><code>输入: [1,2,3,4]
输出: false
</code></pre><p>示例 3:</p>
<pre><code>输入: [1,1,1,3,3,4,3,2,4,2]
输出: true
</code></pre><p>思路：首先对数组进行排序，然后判断是否存在前后两个元素相等的情况。</p>
<p>代码：</p>
<pre><code>bool containsDuplicate(vector&lt;int&gt;&amp; nums) {
       if (nums.size() == 0)
           return false;
       sort(nums.begin(), nums.end());
       for (int i = 1; i &lt; nums.size(); i++)
       {
           if (nums[i] == nums[i-1])
               return true;
       }
       return false;
   }
</code></pre><p>方法二：利用set的特性，不允许重复的key，判断set和vector的大小即可。</p>
<p>代码：</p>
<pre><code>bool containsDuplicate(vector&lt;int&gt;&amp; nums) {
        if (nums.size() == 0)
            return false;
        set&lt;int&gt; set_i(nums.begin(), nums.end());
        return nums.size() &gt; set_i.size();   
    }
</code></pre><h3 id="219-存在重复元素Ⅱ"><a href="#219-存在重复元素Ⅱ" class="headerlink" title="219. 存在重复元素Ⅱ"></a>219. 存在重复元素Ⅱ</h3><p>给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。</p>
<p>示例 1:</p>
<pre><code>输入: nums = [1,2,3,1], k = 3
输出: true
</code></pre><p>示例 2:</p>
<pre><code>输入: nums = [1,0,1,1], k = 1
输出: true
</code></pre><p>示例 3:</p>
<pre><code>输入: nums = [1,2,3,1,2,3], k = 2
输出: false
</code></pre><p>思路：创建一个map存储相同值的数量，如果map中存储对应元素，则判断个数是否已经大于k，如果不大于k，则将map的value加1；如果map中没有对应元素，则插入一个pair。</p>
<p>代码：</p>
<pre><code>bool containsNearbyDuplicate(vector&lt;int&gt;&amp; nums, int k)     {
    if (nums.size() &lt;= 1)
        return false;
    map&lt;int, int&gt; map_i_i;
    for (int i = 0; i &lt; nums.size(); i++)
    {
        if (map_i_i.count(nums[i]))
        {
            if (i - map_i_i[nums[i]] &lt;= k)
                return true;
            else
                map_i_i[nums[i]] = i;
        }
        else
            map_i_i.insert(pair&lt;int, int&gt;(nums[i], i));
    }
    return false;
}
</code></pre><h3 id="268-缺失数字"><a href="#268-缺失数字" class="headerlink" title="268. 缺失数字"></a>268. 缺失数字</h3><p>给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。</p>
<p>示例 1:</p>
<pre><code>输入: [3,0,1]
输出: 2
</code></pre><p>示例 2:</p>
<pre><code>输入: [9,6,4,2,3,5,7,0,1]
输出: 8
</code></pre><p>说明:</p>
<p>你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?</p>
<p>思路： 求和法： 将1到元素个数+1中间所有元素的和减去数组中所有元素，得到的结果就是缺失的元素。</p>
<p>代码：</p>
<pre><code> int missingNumber(vector&lt;int&gt;&amp; nums) {
       int len = nums.size();
    int sum = len * (len + 1) / 2;
    for (int i = 0; i &lt; len; i++)
        sum -= nums[i];
    int sum = 0;
    for (int i = 0; i &lt; nums.size(); i++ )
        sum = sum^(i+1)^(nums[i]);
    return sum;
}
</code></pre><p>异或法：间每个元素和1~n异或，最后得到的结果就是确实的元素</p>
<pre><code>int missingNumber(vector&lt;int&gt;&amp; nums) {
       int len = nums.size();
    int sum = 0;
    for (int i = 0; i &lt; nums.size(); i++ )
        sum = sum^(i+1)^(nums[i]);
    return sum;
}
</code></pre><h3 id="283-移动零"><a href="#283-移动零" class="headerlink" title="283. 移动零"></a>283. 移动零</h3><p>给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。</p>
<p>示例:</p>
<pre><code>输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
</code></pre><p>说明:</p>
<ul>
<li>必须在原数组上操作，不能拷贝额外的数组。</li>
<li>尽量减少操作次数。</li>
</ul>
<p>思路： 双指针法：定义一个指针记录需要覆盖的元素，最后将末尾的元素全部赋值为0。</p>
<p>可以先把所有非0的元素移到前面，然后将后面的位置补0。 使用指针i，指向需要插入的下标，使用指针j指向遍历的下标。遍历一遍，如果j指向的位置为0，则i不变，j++后移；如果j指向的位置不为0，则将j位置的元素值赋值到i位置，然后i++。</p>
<p>代码：</p>
<pre><code>void moveZeroes(vector&lt;int&gt;&amp; nums) {
    int res = 0;
    for (int i = 0; i &lt; nums.size(); i++)
    {
        if (nums[i] != 0)
        {
            nums[res] = nums[i];
            res++;
        }
    }
    for (int j = res; j &lt; nums.size(); j++)
        nums[j] = 0;
}
</code></pre><h3 id="414-第三大的数"><a href="#414-第三大的数" class="headerlink" title="414. 第三大的数"></a>414. 第三大的数</h3><p>给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。</p>
<p>示例 1:</p>
<pre><code>输入: [3, 2, 1]

输出: 1

解释: 第三大的数是 1.
</code></pre><p>示例 2:</p>
<pre><code>输入: [1, 2]

输出: 2

解释: 第三大的数不存在, 所以返回最大的数 2 .
</code></pre><p>示例 3:</p>
<pre><code>输入: [2, 2, 3, 1]

输出: 1

解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。
存在两个值为2的数，它们都排第二。
</code></pre><p>思路：首先对元素进行排序（从小到大），设置一个count，遇到两个不相等的，就减1，当count等于0时，返回当前元素。如果没有就返回最大元素。</p>
<p>代码：</p>
<pre><code>int thirdMax(vector&lt;int&gt;&amp; nums) {
    sort(nums.begin(), nums.end());
    int count = 2;
    for (int  i = nums.size()-1; i &gt;= 1; i--)
    {
        if (nums[i] != nums[i-1])
        {
            count--;
        }
        if (count == 0)
        {
            return nums[i-1];
        }
    }
    return nums[nums.size()-1];
}
</code></pre><p>思路： 利用set去重，而且set是自动排序的，从小到大排序，然后集合大小小于3，直接返回最大的元素，否则往后退两个元素。</p>
<p>代码：</p>
<pre><code>int thirdMax(vector&lt;int&gt;&amp; nums) {
    //采用set去重
    set&lt;int&gt; set_i;
    for(int i = 0; i &lt; nums.size(); i++)
        set_i.insert(nums[i]);
    set&lt;int&gt;::iterator ite = set_i.end();
    if  (set_i.size() &lt; 3)  
    {
        ite--;
        return *ite;
    }
    else
    {
        ite--;
        ite--;
        ite--;
        return *ite;
    }

}
</code></pre><h3 id="448-找到所有数组中消失的数字"><a href="#448-找到所有数组中消失的数字" class="headerlink" title="448. 找到所有数组中消失的数字"></a>448. 找到所有数组中消失的数字</h3><p>给定一个范围在  1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。</p>
<p>找到所有在 [1, n] 范围之间没有出现在数组中的数字。</p>
<p>您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。</p>
<p>示例:</p>
<pre><code>输入:
[4,3,2,7,8,2,3,1]

输出:
[5,6]
</code></pre><p>思路：原理是遍历数组中所有元素，将元素值 - 1对应下标处的值取对应的负数作为标记，最后数组中依然大于0的即为未出现的元素</p>
<p>代码：</p>
<pre><code>vector&lt;int&gt; findDisappearedNumbers(vector&lt;int&gt;&amp; nums) {
    vector&lt;int&gt; res;
    for (int i = 0; i &lt; nums.size(); i++)
        nums[abs(nums[i])-1] = -abs(nums[abs(nums[i])-1]);
    for (int i = 0; i &lt; nums.size(); i++)
        if (nums[i] &gt; 0)
            res.push_back(i+1);
    return res;
}
</code></pre><h3 id="485-最大连续的个数"><a href="#485-最大连续的个数" class="headerlink" title="485. 最大连续的个数"></a>485. 最大连续的个数</h3><p>给定一个二进制数组， 计算其中最大连续1的个数。</p>
<p>示例 1:</p>
<pre><code>输入: [1,1,0,1,1,1]
输出: 3
解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.
</code></pre><p>注意：</p>
<ul>
<li>输入的数组只包含 0 和1。</li>
<li>输入数组的长度是正整数，且不超过 10,000。</li>
</ul>
<p>思路： count记录连续1的个数，如果遇到0，就将count重置为0，每次取最大的count。</p>
<p>代码：</p>
<pre><code>int findMaxConsecutiveOnes(vector&lt;int&gt;&amp; nums) {
    int count = 0;
    int m = 0;
    for (int i = 0; i &lt; nums.size(); i++)
    {
        if (nums[i] == 1)
            count++;
        else
            count = 0;
        m = max(m, count);
    }
    return m;
}
</code></pre><h3 id="532-数组中的K-diff数对"><a href="#532-数组中的K-diff数对" class="headerlink" title="532. 数组中的K-diff数对"></a>532. 数组中的K-diff数对</h3><p>给定一个整数数组和一个整数 k, 你需要在数组里找到不同的 k-diff 数对。这里将 k-diff 数对定义为一个整数对 (i, j), 其中 i 和 j 都是数组中的数字，且两数之差的绝对值是 k.</p>
<p>示例 1:</p>
<pre><code>输入: [3, 1, 4, 1, 5], k = 2
输出: 2
解释: 数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。
尽管数组中有两个1，但我们只应返回不同的数对的数量。
</code></pre><p>示例 2:</p>
<pre><code>输入:[1, 2, 3, 4, 5], k = 1
输出: 4
解释: 数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和 (4, 5)。
</code></pre><p>示例 3:</p>
<pre><code>输入: [1, 3, 1, 5, 4], k = 0
输出: 1
解释: 数组中只有一个 0-diff 数对，(1, 1)。
</code></pre><p>注意:</p>
<ul>
<li>数对 (i, j) 和数对 (j, i) 被算作同一数对。</li>
<li>数组的长度不超过10,000。</li>
<li>所有输入的整数的范围在 [-1e7, 1e7]。</li>
</ul>
<p>思路：首先对于k=0的情况单独分析，直接找相同的元素。对于其他情况，将元素放入一个集合中进行去重，然后判断每个元素+k是否在集合中。</p>
<p>代码：</p>
<pre><code>int findPairs(vector&lt;int&gt;&amp; nums, int k) {
    map&lt;int, int&gt; map_i_i;
    int count = 0;
    if (k &lt; 0)
        return 0;
    if (k == 0)
    {
        for (int i = 0; i &lt; nums.size(); i++)
        {
            if (map_i_i.find(nums[i]) != map_i_i.end())
                map_i_i[nums[i]]++;
            else
                map_i_i[nums[i]] = 1;
            if (map_i_i[nums[i]] == 2)
                count++;
        }
        return count;
    }
    set&lt;int&gt; set_i(nums.begin(), nums.end());
    auto ite = set_i.begin();
    while (ite != set_i.end())
    {
        if (set_i.find(*ite+k) != set_i.end())
            count ++;
        ite++;
    }
    return count;
}
</code></pre><h3 id="561-数组拆分Ⅰ"><a href="#561-数组拆分Ⅰ" class="headerlink" title="561. 数组拆分Ⅰ"></a>561. 数组拆分Ⅰ</h3><p>给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从1 到 n 的 min(ai, bi) 总和最大。</p>
<p>示例 1:</p>
<pre><code>输入: [1,4,3,2]

输出: 4
解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).
</code></pre><p>提示:</p>
<ul>
<li>n 是正整数,范围在 [1, 10000].</li>
<li>数组中的元素范围在 [-10000, 10000].</li>
</ul>
<p>思路：首先对数组进行排序，然后取一个元素，隔一个元素再去下一个元素。</p>
<p>代码：</p>
<pre><code>int arrayPairSum(vector&lt;int&gt;&amp; nums) {
    sort(nums.begin(), nums.end());
    int sum = 0;
    for (int i = 0; i &lt; nums.size(); i+=2)
    {
        sum += nums[i];
    }
    return sum;
}
</code></pre><h3 id="566-重塑矩阵"><a href="#566-重塑矩阵" class="headerlink" title="566. 重塑矩阵"></a>566. 重塑矩阵</h3><p>在MATLAB中，有一个非常有用的函数 reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。</p>
<p>给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。</p>
<p>重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。</p>
<p>如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。</p>
<p>示例 1:</p>
<pre><code>输入: 
nums = 
[[1,2],
 [3,4]]
r = 1, c = 4
输出: 
[[1,2,3,4]]
解释:
行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。
</code></pre><p>示例 2:</p>
<pre><code>输入: 
nums = 
[[1,2],
 [3,4]]
r = 2, c = 4
输出: 
[[1,2],
 [3,4]]
解释:
没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。
</code></pre><p>注意：</p>
<ul>
<li>给定矩阵的宽和高范围在 [1, 100]。</li>
<li>给定的 r 和 c 都是正数。</li>
</ul>
<p>思路：首先判断重塑矩阵的大小是否能够容纳原始矩阵的所有元素。然后，将原始矩阵的所有元素看成是一个1×n的矩阵，并将元素依次放入重塑矩阵中。</p>
<p>这里重点掌握二维矩阵的创建和使用。</p>
<pre><code>vector&lt;vector&lt;int&gt;&gt; ans(r);
for (auto i : r)
    ans[i] = vector&lt;int&gt;(c);
</code></pre><p>代码：</p>
<pre><code>vector&lt;vector&lt;int&gt;&gt; matrixReshape(vector&lt;vector&lt;int&gt;&gt;&amp; nums, int r, int c) {
    int row = nums.size();
    int column = nums[0].size();
    if (r * c &gt;  row * column)
        return nums;
    int i = 0;
    vector&lt;vector&lt;int&gt; &gt; ans(row*column/c); 
    while (i &lt; row * column)
    {
        if (i%c == 0)
            ans[i/c] = vector&lt;int&gt;(c);
        ans[i/c][i%c] = nums[i/column][i%column];
        i++;
    }
    return ans;
}
</code></pre><h3 id="581-最短无序连续子数组"><a href="#581-最短无序连续子数组" class="headerlink" title="581. 最短无序连续子数组"></a>581. 最短无序连续子数组</h3><p>给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。</p>
<p>你找到的子数组应是最短的，请输出它的长度。</p>
<p>示例 1:</p>
<pre><code>输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
</code></pre><p>说明 :</p>
<ul>
<li>输入的数组长度范围在 [1, 10,000]。</li>
<li>输入的数组可能包含重复元素 ，所以升序的意思是&lt;=。</li>
</ul>
<p>思路：首先对元素进行排序，然后两个指针分别从最开头和最末尾开始，判断是否等于排序好的元素，如果不相等就停止，最后，如果两个指针相等，则答案是0，否则答案就是两个指针之查减一。</p>
<p>代码：</p>
<pre><code>int findUnsortedSubarray(vector&lt;int&gt;&amp; nums) {
    int i = 0;
    int j = nums.size()-1;
    vector&lt;int&gt;  temp(nums.begin(), nums.end());
    sort(temp.begin(), temp.end());
    while(i &lt; j)
    {
        if (temp[i] != nums[i])
            break;
        i++;
    }
    while (j &gt; i)
    {
        if (temp[j] != nums[j])
            break;
        j--;
    }
    return i == j ? 0 : j - i + 1;
}
</code></pre><h3 id="605-种花问题"><a href="#605-种花问题" class="headerlink" title="605. 种花问题"></a>605. 种花问题</h3><p>假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。</p>
<p>给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。</p>
<p>示例 1:</p>
<pre><code>输入: flowerbed = [1,0,0,0,1], n = 1
输出: True
</code></pre><p>示例 2:</p>
<pre><code>输入: flowerbed = [1,0,0,0,1], n = 2
输出: False
</code></pre><p>注意:</p>
<ul>
<li>数组内已种好的花不会违反种植规则。</li>
<li>输入的数组长度范围为 [1, 20000]。</li>
<li>n 是非负整数，且不会超过输入数组的大小。</li>
</ul>
<p>方法一：</p>
<p>思路：记录0的个数，len个连续0可以放入(len-1)/2个1，最后还需要考虑末尾的时候，两个零就可以放入一个1。</p>
<p>代码：</p>
<pre><code>bool canPlaceFlowers(vector&lt;int&gt;&amp; flowerbed, int n) {
    int len = 1, ans = 0;
    for(auto i : flowerbed)
    {
        if (i)
        {
            ans += (len-1)/2;
            len = 0;
        }
        else
            len++;
    }
    ans += len/2;
    return ans &gt;= n;
}
</code></pre><p>方法二：</p>
<p>思路：判断当前位置是否为0，以及前一个位置是否为0或者当前处于第一个元素，并且后一个位置为0或者当前处于最后一个元素，如果当前可以放入一个1，则直接向后跳两步，否则跳一步。</p>
<p>代码：</p>
<pre><code>bool canPlaceFlowers(vector&lt;int&gt;&amp; flowerbed, int n) {
    int i = 0;
    int len = flowerbed.size();
    while(i &lt; len &amp;&amp; n != 0)
    {
        if (flowerbed[i] == 0 &amp;&amp; (i == 0 || flowerbed[i-1] == 0) &amp;&amp; (i == len-1 || flowerbed[i+1] == 0))
        {
            n--;
            i+=2;
        }
        else
            i++;
    }
    return n == 0;
}
</code></pre><h3 id="628-三个数的最大乘积"><a href="#628-三个数的最大乘积" class="headerlink" title="628. 三个数的最大乘积"></a>628. 三个数的最大乘积</h3><p>给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。</p>
<p>示例 1:</p>
<pre><code>输入: [1,2,3]
输出: 6
</code></pre><p>示例 2:</p>
<pre><code>输入: [1,2,3,4]
输出: 24
</code></pre><p>注意:</p>
<ul>
<li>给定的整型数组长度范围是[3,10^4]，数组中所有的元素范围是[-1000, 1000]。</li>
<li>输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。</li>
</ul>
<p>思路：首先对数组进行排序，末尾的元素一定是需要三个数之一；然后判断是取前面两个元素还是后面两个元素：如果倒数第二元素小于零，则一定是取前面两个元素；如果第一个和第二元素小于零，并且两者的乘积大于倒数第二和第三两个元素之积，则一定是取前面两个元素。否则取倒数第二和第三个元素。</p>
<p>代码：</p>
<pre><code>int maximumProduct(vector&lt;int&gt;&amp; nums) {
    if (nums.size() &lt;= 2)
        return 0;
    sort(nums.begin(), nums.end());
    int ans = 1;
    ans *= nums[nums.size()-1];
    if (nums[nums.size()-2] &lt; 0 || (nums[0] &lt; 0 &amp;&amp; nums[1] &lt; 0 &amp;&amp; abs(nums[0])*abs(nums[1]) &gt; nums[nums.size()-2]*nums[nums.size()-3]) )
        ans *= nums[0]*nums[1];
    else
        ans *= nums[nums.size()-2]*nums[nums.size()-3];
    return ans;
}
</code></pre><h3 id="643-子数组最大平均数-I"><a href="#643-子数组最大平均数-I" class="headerlink" title="643 子数组最大平均数 I"></a>643 子数组最大平均数 I</h3><p>给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。</p>
<p>示例 1:</p>
<pre><code>输入: [1,12,-5,-6,50,3], k = 4
输出: 12.75
解释: 最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
</code></pre><p>注意:</p>
<ul>
<li>1 &lt;= k &lt;= n &lt;= 30,000。</li>
<li>所给数据范围 [-10,000，10,000]。</li>
</ul>
<p>思路： 窗口平滑。首先计算k元素的和，然后从每次减去开头第i个元素的值，加上第k+i个元素的值，每次取最大和。</p>
<p>代码：</p>
<pre><code>double findMaxAverage(vector&lt;int&gt;&amp; nums, int k) {
    int max = 0;
    for (int i = 0; i &lt; k; i++)
        max += nums[i];
    int max1 = max;
    int max2 = 0;
    for (int i = 1; i &lt; nums.size() - k + 1; i++)
    {
        max2 = max1 - nums[i-1] + nums[k+i-1];
        max = max &gt; max2 ? max : max2;
        max1 = max2;
    }
    return (double)(max)/k;
}
</code></pre><h3 id="661-图片平滑器"><a href="#661-图片平滑器" class="headerlink" title="661. 图片平滑器"></a>661. 图片平滑器</h3><p>包含整数的二维矩阵 M 表示一个图片的灰度。你需要设计一个平滑器来让每一个单元的灰度成为平均灰度 (向下舍入) ，平均灰度的计算是周围的8个单元和它本身的值求平均，如果周围的单元格不足八个，则尽可能多的利用它们。</p>
<p>示例 1:</p>
<pre><code>输入:
[[1,1,1],
 [1,0,1],
 [1,1,1]]
输出:
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
解释:
对于点 (0,0), (0,2), (2,0), (2,2): 平均(3/4) = 平均(0.75) = 0
对于点 (0,1), (1,0), (1,2), (2,1): 平均(5/6) = 平均(0.83333333) = 0
对于点 (1,1): 平均(8/9) = 平均(0.88888889) = 0
</code></pre><p>注意:</p>
<ul>
<li>给定矩阵中的整数范围为 [0, 255]。</li>
<li>矩阵的长和宽的范围均为 [1, 150]。</li>
</ul>
<p>思路: 考虑所有情况。如果位置为第一行，则只需要考虑数组所在的行和下一行；如果位置为最后一行，则只需要考虑数字所在的行和前一行。如果位置位于第一列，则只需要考虑数字所在的列和后一列；如果位置位于最后一列，则只需要考虑数字所在的列和前一列。</p>
<p>代码：</p>
<p>   vector&lt;vector<int>&gt; imageSmoother(vector&lt;vector<int>&gt;&amp; M) {<br>        vector&lt;vector<int> &gt;  ans(M.size());<br>        int sum = 0;<br>        int count = 0;<br>        for(int i = 0; i &lt; M.size(); i++)<br>        {<br>            ans[i] = vector<int>(M[0].size());<br>            for (int j = 0; j &lt; M[0].size(); j++)<br>            {<br>                sum = 0;<br>                count = 0;<br>                //计算左侧一列<br>                if (j &gt; 0)<br>                {<br>                    sum += M[i][j-1];<br>                    count++;<br>                    if (i &gt; 0)<br>                    {<br>                        sum += M[i-1][j-1];<br>                        count++;<br>                    }<br>                    if (i &lt; M.size()-1)<br>                    {<br>                        sum += M[i+1][j-1];<br>                        count++;<br>                    }<br>                }<br>                //计算中间一列<br>                sum += M[i][j];<br>                count++;<br>                if (i &gt; 0)<br>                {<br>                    sum += M[i-1][j];<br>                    count++;<br>                }<br>                if (i &lt; M.size()-1)<br>                {<br>                    sum += M[i+1][j];<br>                    count++;<br>                }<br>                //计算右侧一列<br>                if (j &lt; M[0].size() - 1)<br>                {<br>                    sum += M[i][j+1];<br>                    count++;<br>                    if (i &gt; 0)<br>                    {<br>                        sum += M[i-1][j+1];<br>                        count++;<br>                    }<br>                    if (i &lt; M.size() - 1)<br>                    {<br>                        sum += M[i+1][j+1];<br>                        count++;<br>                    }<br>                }<br>                ans[i][j] = sum / count;<br>            }<br>        }<br>        return ans;</int></int></int></int></p>
<pre><code>}
</code></pre><h3 id="665-非递减数列"><a href="#665-非递减数列" class="headerlink" title="665. 非递减数列"></a>665. 非递减数列</h3><p>给定一个长度为 n 的整数数组，你的任务是判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。</p>
<p>我们是这样定义一个非递减数列的： 对于数组中所有的 i (1 &lt;= i &lt; n)，满足 array[i] &lt;= array[i + 1]。</p>
<p>示例 1:</p>
<pre><code>输入: [4,2,3]
输出: True
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
</code></pre><p>示例 2:</p>
<pre><code>输入: [4,2,1]
输出: False
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
</code></pre><p>说明:  n 的范围为 [1, 10,000]。</p>
<p>思路：    </p>
<pre><code>如果出现 a[i] &gt; a[i+1]   改变一个数 就面临两种选择
1. 把a[i]变大
2. 把a[i+1] 变小
这两种选择其实是有依据的 需要比较a[i-1] 与 a[i+1]的值
eg.  ... 1 4 3 ...   只能选择把4变小   ... 3 4 1 ... 只能选择把1变大
改变完之后，记录改变次数，再检测是否升序
如果次数大于1，至少改了两次 返回false

先让前两个有序
因为没有左边没有数 所以对于前两个数来说，最佳选择就是吧 a[0] 变小
</code></pre><p>代码：</p>
<pre><code>bool checkPossibility(vector&lt;int&gt;&amp; nums) {
    // 数组个数小于2个 一定可以
    if (nums.size() &lt; 3)
        return true;
    int count = 0;
    if (nums[0] &gt; nums[1])
    {
        count++;
        nums[0] = nums[1];
    }
    for (int i = 1; i &lt; nums.size()-1;  i++)
    {
        int right = nums[i+1];
        if (nums[i] &gt; right)
        {
            count++;
            if (count &gt; 1)
                return false;
            int left = nums[i-1];
            if (left &gt; right)
                nums[i+1] = nums[i];
            else
                nums[i] = left;
        }
    }
    return true;
}
</code></pre><h3 id="746-使用最小花费爬楼梯"><a href="#746-使用最小花费爬楼梯" class="headerlink" title="746. 使用最小花费爬楼梯"></a>746. 使用最小花费爬楼梯</h3><p>数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost<a href="索引从0开始">i</a>。</p>
<p>每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。</p>
<p>您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。</p>
<p>示例 1:</p>
<pre><code>输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。
</code></pre><p> 示例 2:</p>
<pre><code>输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。
</code></pre><p>注意：</p>
<ul>
<li>cost 的长度将会在 [2, 1000]。</li>
<li>每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。</li>
</ul>
<p>思路：动态规划。最小子问题，每一步i的最小从花费等于前一步开销加上当前i阶梯开销和前两步的开销加上当前i阶梯的开销中的最小值。对于，最后一步，如果是前两步的开销必须加上最后一步的开销，而对于前一步的开销就不需要加上最后一步的开销。</p>
<p>代码：</p>
<pre><code>int minCostClimbingStairs(vector&lt;int&gt;&amp; cost) {
    if (cost.size() == 0)
        return 0;
    if (cost.size() == 1)
        return cost[0];
    if (cost.size() == 2)
        return min(cost[0], cost[1]);
    vector&lt;int&gt; dp(cost.size());
    dp[0] = cost[0];
    dp[1] = cost[1];
    int i;
    for (i = 2; i &lt; cost.size()-1; i++)
    {
        dp[i] = min(dp[i-1]+cost[i], dp[i-2]+cost[i]);
    }
    dp[i] = min(dp[i-1], dp[i-2]+cost[i]);
    return dp[i];
}
</code></pre><h2 id="动态规划"><a href="#动态规划" class="headerlink" title="动态规划"></a>动态规划</h2><h3 id="5-最大子序和"><a href="#5-最大子序和" class="headerlink" title="5. 最大子序和"></a>5. 最大子序和</h3><p>给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。</p>
<p>示例:</p>
<pre><code>输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
</code></pre><p>进阶:</p>
<p>如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。</p>
<p>思路： 子问题是每次判断前面所有的和是否大于0，如果小于零，则对于求最大和没有作用，所以直接省略前面的和。</p>
<p>代码：</p>
<pre><code>int maxSubArray(vector&lt;int&gt;&amp; nums) {
    int n = nums.size();
    int * dp = new int[n];
    dp[0] = nums[0];
    int m = nums[0];
    for (int i = 1; i &lt; n; i++)
    {
        dp[i] = nums[i] + (dp[i-1] &gt; 0 ?  dp[i-1] : 0);
        m = max(m, dp[i]);
    }
    return m;
}
</code></pre><h3 id="70-爬楼梯"><a href="#70-爬楼梯" class="headerlink" title="70 爬楼梯"></a>70 爬楼梯</h3><p>假设你正在爬楼梯。需要 n 阶你才能到达楼顶。</p>
<p>每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？</p>
<p>注意：给定 n 是一个正整数。</p>
<p>示例 1：</p>
<pre><code>输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶
</code></pre><p>示例 2：</p>
<pre><code>输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶
</code></pre><p>思路：初始问题，一个台阶只有一种爬法；两个台阶有两种爬法。而对于i个台阶，其爬法为：i-1个台阶爬法和i-2个台阶的爬法之和。</p>
<p>代码：</p>
<pre><code>int climbStairs(int n) {
    if (n == 1)
        return 1;
    int * dp = new int[n+1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i &lt;= n; i++)
    {
        dp[i] =dp[i-1] + dp[i-2]; 
    }
    return dp[n];
    /*if (n == 1) //递归实现
        return 1;
    if (n == 2)
        return 2;
    int a = climbStairs(n-1) + climbStairs(n-2);
    return a;*/
}
</code></pre><h3 id="121-买卖股票的最佳时机"><a href="#121-买卖股票的最佳时机" class="headerlink" title="121 买卖股票的最佳时机"></a>121 买卖股票的最佳时机</h3><p>给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。</p>
<p>如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。</p>
<p>注意你不能在买入股票前卖出股票。</p>
<p>示例 1:</p>
<pre><code>输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
</code></pre><p>示例 2:</p>
<pre><code>输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
</code></pre><p>思路： 每次第i个元素和前面i个元素中最小值，并将i个元素减去最小值，然后取差中的最大值。</p>
<p>其实这是一个求最低谷到最高峰的问题。</p>
<p>代码：</p>
<pre><code>int maxProfit(vector&lt;int&gt;&amp; prices) {
    if (prices.size() &lt;= 1)
        return 0;
    int minprices = prices[0];  
    int maxprofit = 0;
    for (int i = 1; i &lt; prices.size(); i++)
    {

        minprices = min(minprices, prices[i]);
        int profit =  prices[i] - minprices;
        maxprofit = max(profit, maxprofit);
    }
    return maxprofit;
}
</code></pre><h3 id="198-打家劫舍"><a href="#198-打家劫舍" class="headerlink" title="198 打家劫舍"></a>198 打家劫舍</h3><p>你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。</p>
<p>给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。</p>
<p>示例 1:</p>
<pre><code>输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
</code></pre><p>示例 2:</p>
<pre><code>输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。
</code></pre><p>思路： 动态规划。初始问题，只有一个房屋是，小偷收益就是该房间的。如果两个房屋，小偷收益就是两个房屋中的最大值。而对于第i个房屋，小偷的最大收益为当前房屋i的金额加上偷第i-2个房屋的收益和偷第i-1个房屋的收益的最大值。</p>
<p>代码：</p>
<pre><code>int rob(vector&lt;int&gt;&amp; nums) {
    if (nums.size() == 0)
        return 0;
    if (nums.size() == 1)
        return nums[0];
    vector&lt;int&gt; dp(nums.size());
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    for (int i = 2; i &lt; nums.size(); i++)
    {
        dp[i] = max(dp[i-2]+nums[i], dp[i-1]);
    }
    return dp[nums.size()-1];
}
</code></pre><h3 id="213-打家劫舍-Ⅱ（中等）"><a href="#213-打家劫舍-Ⅱ（中等）" class="headerlink" title="213 打家劫舍 Ⅱ（中等）"></a>213 打家劫舍 Ⅱ（中等）</h3><p>你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。</p>
<p>给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。</p>
<p>示例 1:</p>
<pre><code>输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
</code></pre><p>示例 2:</p>
<pre><code>输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。
</code></pre><p>思路：分两种情况，分别计算两种情况下的最大收益，即两次动态规划。第一种情况，即偷第一间房屋，这样就不能偷最后一间房屋；第二种情况，不偷第一间放我，这样就可以偷最后一间房屋。</p>
<p>代码：</p>
<pre><code>int rob(vector&lt;int&gt;&amp; nums) {
    vector&lt;int&gt; dp1(nums.size());
    vector&lt;int&gt; dp2(nums.size());
    if (nums.size()  == 0)
        return 0;
    if (nums.size() == 1)
        return nums[0];
    dp1[0] = nums[0];
    dp1[1] = max(nums[0], nums[1]);
    for (int i = 2; i &lt; nums.size()-1; i++)
    {
        dp1[i] = max(dp1[i-1], nums[i]+dp1[i-2]);
    }
    dp2[0] = 0;
    dp2[1] = nums[1];
    for (int i = 2; i &lt; nums.size(); i++)
    {
        dp2[i] = max(dp2[i-1], nums[i] + dp2[i-2]);
    }
    return max(dp1[nums.size()-2], dp2[nums.size()-1]);
}
</code></pre><h3 id="303-区域和检索-数组不可变"><a href="#303-区域和检索-数组不可变" class="headerlink" title="303  区域和检索 - 数组不可变"></a>303  区域和检索 - 数组不可变</h3><p>给定一个整数数组  nums，求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和，包含 i,  j 两点。</p>
<p>示例：</p>
<pre><code>给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()

sumRange(0, 2) -&gt; 1
sumRange(2, 5) -&gt; -1
sumRange(0, 5) -&gt; -3
</code></pre><p>说明:</p>
<ul>
<li>你可以假设数组不可变。</li>
<li>会多次调用 sumRange 方法。</li>
</ul>
<p>思路：创建一个共享数组。构造函数往共享数组中写数据，该数组中元素是构造函数参数数组中前i个元素的和，而sumRange()函数返回结果。</p>
<p>代码：</p>
<pre><code>class NumArray {
public:
    //创建一个数字记录前面计算过的值，避免重复计算
    vector&lt;int&gt; num;
    NumArray(vector&lt;int&gt;&amp; nums) {
        num.push_back(0);
        int sum = 0;
        for (int i = 0; i &lt; nums.size(); i++)
        {
            sum += nums[i];
            num.push_back(sum);
        }
    }

    int sumRange(int i, int j) {
        return num[j+1] - num[i];
    }
};
</code></pre><h3 id="746-使用最小花费爬楼梯-1"><a href="#746-使用最小花费爬楼梯-1" class="headerlink" title="746 使用最小花费爬楼梯"></a>746 使用最小花费爬楼梯</h3><p>数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost [i] (索引从0开始)。</p>
<p>每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。</p>
<p>您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。</p>
<p>示例 1:</p>
<pre><code>输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。
</code></pre><p>示例 2:</p>
<pre><code>输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。
</code></pre><p>注意：</p>
<ul>
<li>cost 的长度将会在 [2, 1000]。</li>
<li>每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。</li>
</ul>
<p>思路：动态规划问题。最小问题就是对于第i个台阶，所需的总开销就是当前台阶的开销加上前一个台阶和前两个台阶最小开销之和。</p>
<p>需要注意的是，最后一步，如果从第i-1步直接走上去，就不需要加上第i个台阶的开销。而对于从第i-2步走得话，就需要加上第i个台阶得开销。</p>
<p>代码：</p>
<pre><code>int minCostClimbingStairs(vector&lt;int&gt;&amp; cost) {
    if (cost.size() == 0)
        return 0;
    if (cost.size() == 1)
        return cost[0];
    if (cost.size() == 2)
        return min(cost[0], cost[1]);
    vector&lt;int&gt; dp(cost.size());
    dp[0] = cost[0];
    dp[1] = cost[1];
    int i;
    for (i = 2; i &lt; cost.size()-1; i++)
    {
        dp[i] = min(dp[i-1]+cost[i], dp[i-2]+cost[i]);
    }
    //最后一步需要单独考虑，可能最后一个台阶可以直接跳过
    dp[i] = min(dp[i-1], dp[i-2]+cost[i]);
    return dp[i];
}
</code></pre><h4 id="1025-除数博弈"><a href="#1025-除数博弈" class="headerlink" title="1025. 除数博弈"></a>1025. 除数博弈</h4><p>爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。</p>
<p>最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：</p>
<ul>
<li>选出任一 x，满足 0 &lt; x &lt; N 且 N % x == 0 。</li>
<li>用 N - x 替换黑板上的数字 N 。</li>
</ul>
<p>如果玩家无法执行这些操作，就会输掉游戏。</p>
<p>只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。</p>
<p>示例 1：</p>
<pre><code>输入：2
输出：true
解释：爱丽丝选择 1，鲍勃无法进行操作。
示例 2：

输入：3
输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。
</code></pre><p>提示：</p>
<pre><code>1 &lt;= N &lt;= 1000
</code></pre><p>方法一： 归纳法</p>
<p>思路： 首先需要明确的是，对于一个确定的数N，只可能赢或者输，不可能存在不确定的情况，也就是只要对于N能存在赢的情况就是赢，那么该问题演变为，如果Alice拿到N是输的话，那么她拿到N+1一定为赢，因为拿到N+1时，她可以只取1，那么Bob就会拿到N，Bob就会输，所以这时候奇数偶数，一个为赢另一个为输的问题，我们只需要确定奇数赢还是偶数赢就可以了，依据示例可以看出偶数是赢的</p>
<p>代码：</p>
<pre><code>bool divisorGame(int N) {
    return N % 2 == 0;
}
</code></pre><p>方法二：暴力解法</p>
<p>代码：</p>
<pre><code>bool divisorGame(int N) {
    int count = 0;
    while (N &gt; 1)
    {
        for (int i = 1; i &lt; sqrt(N); i++)
        {
            if (N % i == 0)
            {
                N = N - i;
                count++;
                break;
            }
        }
    }
    return (count % 2) != 0;

}
</code></pre><p>方法三：动态规划DP</p>
<p>代码：</p>
<pre><code>bool divisorGame(int N) {
    if (N &lt; 2)
        return false;
    vector&lt;bool&gt; dp(N+1);
    dp[0] = false;
    dp[1] = false;
    for (int i = 2; i &lt;= N; i++)
        for (int j = 1; j &lt; i; j++)
        {
            if (!dp[i-j] &amp;&amp; i % j == 0)
            {
                dp[i] = true;
                break;
            }
        }
    return dp[N];
}
</code></pre><h2 id="字符串"><a href="#字符串" class="headerlink" title="字符串"></a>字符串</h2><h3 id="415-字符串相加"><a href="#415-字符串相加" class="headerlink" title="415 字符串相加"></a>415 字符串相加</h3><p>给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。</p>
<p>注意：</p>
<ul>
<li>num1 和num2 的长度都小于 5100.</li>
<li>num1 和num2 都只包含数字 0-9.</li>
<li>num1 和num2 都不包含任何前导零。</li>
<li>你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。</li>
</ul>
<p>思路：首先将两个字符串进行转序，创建一个num3字符串记录结构。然后从i=0开始，每次将字符串中的字符转换为整型，然后计算两者的和，如果和大于9，则将和取余转换成字符串加入num3，并将flag设置为1，表示需要进位；否则直接结果放入num3中。最后，判断flag是否为1，如果为1，在num3的末尾添加一个字符1。最后，将num3进行转序得到结果。</p>
<p>代码：</p>
<pre><code>string addStrings(string num1, string num2) {
    reverse(num1.begin(), num1.end());
    reverse(num2.begin(), num2.end());
    string num3;
    int flag = 0;
    int i;
    for (i = 0; i &lt; num1.size() || i &lt; num2.size(); i++)
    {
        int ans = 0, n1 = 0, n2 = 0;
        if (i &lt; num1.size())
            n1 = num1[i] - &apos;0&apos;;
        if (i &lt; num2.size())
            n2 = num2[i] - &apos;0&apos;;
        ans = n1 + n2 + flag;
        if (ans &gt; 9)
        {
            num3.insert(i,1, ans%10 + &apos;0&apos;);
            flag = 1;
        }
        else 
        {
            num3.insert(i,1, ans+&apos;0&apos;);
            flag = 0;
        }
    }
    if (flag == 1)
        num3.append(&quot;1&quot;);
    reverse(num3.begin(), num3.end());
    return num3;
}
</code></pre><h3 id="434-字符串中的单词数"><a href="#434-字符串中的单词数" class="headerlink" title="434 字符串中的单词数"></a>434 字符串中的单词数</h3><p>统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。</p>
<p>请注意，你可以假定字符串里不包括任何不可打印的字符。</p>
<p>示例:</p>
<pre><code>输入: &quot;Hello, my name is John&quot;
输出: 5
</code></pre><p>思路：但前一个字符不为空格，而当前字符串为空格或者为\0时，表示前面出现一个单词。</p>
<p>代码：</p>
<pre><code>int countSegments(string s) {
    int count = 0;
    for (int i = 1; i &lt;= s.size(); i++)
    {
        if (s[i-1] != &apos; &apos; &amp;&amp; (s[i] == &apos; &apos; || s[i] == &apos;\0&apos; ))
            count++;
    }
    return count;
}
</code></pre><h3 id="443-压缩字符串"><a href="#443-压缩字符串" class="headerlink" title="443 压缩字符串"></a>443 压缩字符串</h3><p>题目：</p>
<p>给定一组字符，使用原地算法将其压缩。</p>
<p>压缩后的长度必须始终小于或等于原数组长度。</p>
<p>数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。</p>
<p>在完成原地修改输入数组后，返回数组的新长度。</p>
<p>进阶：<br>你能否仅使用O(1) 空间解决问题？</p>
<p>示例 1：</p>
<pre><code>输入：
[&quot;a&quot;,&quot;a&quot;,&quot;b&quot;,&quot;b&quot;,&quot;c&quot;,&quot;c&quot;,&quot;c&quot;]

输出：
返回6，输入数组的前6个字符应该是：[&quot;a&quot;,&quot;2&quot;,&quot;b&quot;,&quot;2&quot;,&quot;c&quot;,&quot;3&quot;]

说明：
&quot;aa&quot;被&quot;a2&quot;替代。&quot;bb&quot;被&quot;b2&quot;替代。&quot;ccc&quot;被&quot;c3&quot;替代。
</code></pre><p>示例 2：</p>
<pre><code>输入：
[&quot;a&quot;]

输出：
返回1，输入数组的前1个字符应该是：[&quot;a&quot;]

说明：
没有任何字符串被替代。
</code></pre><p>示例 3：</p>
<pre><code>输入：
[&quot;a&quot;,&quot;b&quot;,&quot;b&quot;,&quot;b&quot;,&quot;b&quot;,&quot;b&quot;,&quot;b&quot;,&quot;b&quot;,&quot;b&quot;,&quot;b&quot;,&quot;b&quot;,&quot;b&quot;,&quot;b&quot;]

输出：
返回4，输入数组的前4个字符应该是：[&quot;a&quot;,&quot;b&quot;,&quot;1&quot;,&quot;2&quot;]。

说明：
由于字符&quot;a&quot;不重复，所以不会被压缩。&quot;bbbbbbbbbbbb&quot;被“b12”替代。
注意每个数字在数组中都有它自己的位置。
</code></pre><p>注意：</p>
<ul>
<li>所有字符都有一个ASCII值在[35, 126]区间内。</li>
<li>1 &lt;= len(chars) &lt;= 1000。</li>
</ul>
<p>思路：双指针法。一个指针记录需要存放字母出现次数的位置。当另一个指针指向的字符和后一个字符相等，则计数器count加加，否则如果两个字符不相等，分两种情况，如果count=1，则不需要将count加入到字符串中；否则，得将count放入字符串中，利用<code>to_string()</code>函数将整型转换成字符串，然后一个一个字符添加到字符串中。</p>
<p>代码：</p>
<pre><code>int compress(vector&lt;char&gt;&amp; chars) {
    int r = 0;
    int count = 1;
    for (int i = 0; i &lt; chars.size()-1; i++)
    {
        if (chars[i] == chars[i+1])
            count++;
        else if (chars[i] != chars[i+1] &amp;&amp; count == 1)
        {
            chars[++r] = chars[i+1];
        }
        else
        {
            string temp = to_string(count);
            for (auto c : temp)
                chars[++r] = c;
            chars[++r] = chars[i+1];
            count = 1;
        }
    }
    if (count != 1)
    {
        string temp = to_string(count);
        for (auto c : temp)
            chars[++r] = c;
    }
    return r+1;
}
</code></pre><h3 id="459-重复得子字符串"><a href="#459-重复得子字符串" class="headerlink" title="459 重复得子字符串"></a>459 重复得子字符串</h3><p>给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。</p>
<p>示例 1:</p>
<pre><code>输入: &quot;abab&quot;

输出: True

解释: 可由子字符串 &quot;ab&quot; 重复两次构成。
</code></pre><p>示例 2:</p>
<pre><code>输入: &quot;aba&quot;

输出: False
</code></pre><p>示例 3:</p>
<pre><code>输入: &quot;abcabcabcabc&quot;

输出: True

解释: 可由子字符串 &quot;abc&quot; 重复四次构成。 (或者子字符串 &quot;abcabc&quot; 重复两次构成。)
</code></pre><p>思路：创建一个字符数组，其大小是原字符串大小的2倍减1，然后将字符串除第一个字符之外的所有字符放入数组中，以及将除字符最后一个字符之外的所有字符放入数组中。最后，判断新创建的字符串是否包含原字符串。</p>
<p>注意： strncat(dest, src, n)，将src中的前n个字符追加到str的末尾；strstr(str1, str2)判断str2是否是str1的子串。memset(str, 0, sizeof(str))将str中所有字符初始化为0。</p>
<p>代码：</p>
<pre><code>bool repeatedSubstringPattern(string s) {
    int len = s.size();
    char str1[len+1];
    int i;
    for (i = 0; i &lt; len; i++)
        str1[i] = s[i];
    str1[i] = &apos;\0&apos;;
    char str[2 * len - 1];
    memset(str, 0, sizeof(str));
    strncat(str, str1 + 1, len - 1);
    strncat(str, str1, len - 1);

    return strstr(str, str1);
}
</code></pre><h3 id="520-检测大写字母"><a href="#520-检测大写字母" class="headerlink" title="520. 检测大写字母"></a>520. 检测大写字母</h3><p>给定一个单词，你需要判断单词的大写使用是否正确。</p>
<p>我们定义，在以下情况时，单词的大写用法是正确的：</p>
<ul>
<li>全部字母都是大写，比如”USA”。</li>
<li>单词中所有字母都不是大写，比如”leetcode”。</li>
<li>如果单词不只含有一个字母，只有首字母大写， 比如 “Google”。</li>
</ul>
<p>否则，我们定义这个单词没有正确使用大写字母。</p>
<p>示例 1:</p>
<pre><code>输入: &quot;USA&quot;
输出: True
</code></pre><p>示例 2:</p>
<pre><code>输入: &quot;FlaG&quot;
输出: False
注意: 输入是由大写和小写拉丁字母组成的非空单词。
</code></pre><p>思路： 首先判断首字母是否为大写，用flag=true标记，如果剩余字符中出现大写字母，则将flag设为false，并结束循环；最后判断flag是否为true，为true则返回true。</p>
<p>以上是第一种情况，现在分析第二种和第三种情况，初始化两个计数器，分别记录大写字母的数量和小写字母的数量，通过islower和isupper函数来判断一个字符是否为小写字母和大写字母。最后判断两者的大小是否等于字符串的大小，如果某一个等于字符串大小，则返回true，否则返回false。</p>
<p>代码：</p>
<pre><code>bool detectCapitalUse(string word) {
    int flag = false;
    if (isupper(word[0]))
        flag = true;
    for (int i = 1; i &lt; word.size(); i++)
    {
        if (isupper(word[i]))
        {                    
            flag = false;
            break;
        }    
    }
    if (flag == true)
        return true;
    int up_count = 0;
    int low_count = 0;
    for (int i = 0; i &lt; word.size(); i++)
        if (islower(word[i]))
            low_count++;
        else 
            up_count++;
    if (low_count == word.size() || up_count == word.size())
        return true;
    return false;     
}
</code></pre><p>第二种解法：记录大写字母的数量，如果出现大写字母的数量小于当前字符的下标，则返回false，说明前面出现非连续的大写字母。</p>
<p>代码：</p>
<pre><code>bool detectCapitalUse(string word) {
    int uc = 0;
    for (int i = 0; i &lt; word.size(); i++)
    {
        if (isupper(word[i]) &amp;&amp; uc++ &lt; i)
            return false;
    }
    return uc == word.size() || uc &lt;= 1;
}
</code></pre><h3 id="521-最长特殊序列-Ⅰ"><a href="#521-最长特殊序列-Ⅰ" class="headerlink" title="521 最长特殊序列 Ⅰ"></a>521 最长特殊序列 Ⅰ</h3><p>给定两个字符串，你需要从这两个字符串中找出最长的特殊序列。最长特殊序列定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。</p>
<p>子序列可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列，任何字符串为其自身的子序列。</p>
<p>输入为两个字符串，输出最长特殊序列的长度。如果不存在，则返回 -1。</p>
<p>示例 :</p>
<pre><code>输入: &quot;aba&quot;, &quot;cdc&quot;
输出: 3
解析: 最长特殊序列可为 &quot;aba&quot; (或 &quot;cdc&quot;)
</code></pre><p>说明:</p>
<ul>
<li>两个字符串长度均小于100。</li>
<li>字符串中的字符仅含有 ‘a’~’z’。</li>
</ul>
<p>思路：</p>
<ul>
<li>s1 = ‘ab’,s2 = ‘a’,因为ab是s1独有，所以最长子序列为ab，</li>
<li>s1 = ‘ab’, s2 = ‘ab’, 因为ab是两个串都有，ab排除，a也是两个串都有，排除，b也是两个串都有，排除。所以最长特殊序列不存在，返回-1</li>
<li>通过以上分析，我们可以得出结论，如果：两个串相等（不仅长度相等，内容也相等），那么他们的最长特殊序列不存在。返回-1</li>
<li>如果两个串长度不一样，那么长的串 永远也不可能是 短串的子序列，即len(s1) &gt; len(s2),则最长特殊序列为s1,返回长度大的数</li>
</ul>
<p>注意：</p>
<p>string转换成字符数组转的函数： c_str()</p>
<pre><code>string x = &quot;ab&quot;;
char * y = x.c_str();
</code></pre><p>字符数组转成成string的函数： 直接赋值</p>
<pre><code>const char * x = &quot;abc&quot;;
string y = x;
</code></pre><p>整型转string: to_string()</p>
<pre><code>int a = 10;
string x = a.to_string();
</code></pre><p>strcmp(str1, str2)，比较两个字符串的是否相等（长度和内容相等），str1和str2为字符数组。若str1=str2，则返回零；若str1&lt;str2，则返回负数；若str1&gt;str2，则返回正数。</p>
<p>代码：</p>
<pre><code>  int findLUSlength(string a, string b) {
    return (strcmp(a.c_str(), b.c_str()) ? (a.size()&gt; b.size() ? a.size() : b.size() ): -1);
}
</code></pre><h3 id="541-反转字符串-II"><a href="#541-反转字符串-II" class="headerlink" title="541 反转字符串 II"></a>541 反转字符串 II</h3><p>给定一个字符串和一个整数 k，你需要对从字符串开头算起的每个 2k 个字符的前k个字符进行反转。如果剩余少于 k 个字符，则将剩余的所有全部反转。如果有小于 2k 但大于或等于 k 个字符，则反转前 k 个字符，并将剩余的字符保持原样。</p>
<p>示例:</p>
<pre><code>输入: s = &quot;abcdefg&quot;, k = 2
输出: &quot;bacdfeg&quot;
</code></pre><p>要求:</p>
<ul>
<li>该字符串只包含小写的英文字母。</li>
<li>给定字符串的长度和 k 在[1, 10000]范围内。</li>
</ul>
<p>思路:对字符串进行分隔，然后创建一个临时字符串来存储每个部分的字符串，并利用reverse进行逆转，逆转后将该字符串加入存放结果的字符串中。最后，两种特殊情况进行讨论，即大小k个字符时，以及大于等于k个字符和小于2k。</p>
<p>代码：</p>
<pre><code>string reverseStr(string s, int k) {
    int n = s.size()%(2*k);
    int m = s.size()/(2*k);
    string str;
    for (int i = 0; i &lt; m; i++)
    {
        string temp = string(s.begin()+2*k*i, s.begin()+2*k*(i+1));
        reverse(temp.begin(), temp.end()-k);
        str += temp;
        temp = &quot;&quot;;
    }
    string temp = string(s.begin()+2*k*m, s.end());
    if (n &lt; k)
        reverse(temp.begin(), temp.end());
    if (n &gt;= k &amp;&amp; n &lt; 2*k)
        reverse(temp.begin(), temp.begin()+k);
    str += temp;
    return str;
}
</code></pre><h3 id="551-学生出勤记录"><a href="#551-学生出勤记录" class="headerlink" title="551 学生出勤记录"></a>551 学生出勤记录</h3><p>给定一个字符串来代表一个学生的出勤记录，这个记录仅包含以下三个字符：</p>
<pre><code>&apos;A&apos; : Absent，缺勤
&apos;L&apos; : Late，迟到
&apos;P&apos; : Present，到场
</code></pre><p>如果一个学生的出勤记录中不超过一个’A’(缺勤)并且不超过两个连续的’L’(迟到),那么这个学生会被奖赏。</p>
<p>你需要根据这个学生的出勤记录判断他是否会被奖赏。</p>
<p>示例 1:</p>
<pre><code>输入: &quot;PPALLP&quot;
输出: True
</code></pre><p>示例 2:</p>
<pre><code>输入: &quot;PPALLL&quot;
输出: False
</code></pre><p>思路: 不被奖赏的同学包括：大于等于2个A，或者存在连续3个L。所以，我们只要统计A的个数，以及是否存在连续的3个L，两个条件满足一个就返回false。如果字符串长度小于等于1，则一定会被奖赏，返回true。</p>
<p>代码:</p>
<pre><code>bool checkRecord(string s) {
    if (s.size() &lt;= 1)
        return true;
    int flag1 = 0, flag2 = 0;
    for (int i = 0; i &lt; s.size()-2; i++)
    {
        if (s[i] == &apos;A&apos;)
            flag1 += 1;
        if (s[i] == s[i+1] &amp;&amp; s[i+1] == s[i+2] &amp;&amp; (s[i] == &apos;L&apos;))
            flag2 = 1;
    }
    if ( s[s.size()-1] == &apos;A&apos;)
        flag1  += 1;
    if (s[s.size()-2] == &apos;A&apos;)
        flag1++;
    if (flag1 &gt;= 2 || flag2 == 1)
        return false;
    else
        return true;
}
</code></pre><h2 id="树"><a href="#树" class="headerlink" title="树"></a>树</h2><h3 id="100-相同的树"><a href="#100-相同的树" class="headerlink" title="100 相同的树"></a>100 相同的树</h3><p>给定两个二叉树，编写一个函数来检验它们是否相同。</p>
<p>如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。</p>
<p>示例 1:</p>
<pre><code>输入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true
</code></pre><p>示例 2:</p>
<pre><code>输入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

输出: false
</code></pre><p>示例 3:</p>
<pre><code>输入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

输出: false
</code></pre><p>思路： 递归。最小问题时，但两颗树同时指向空，则返回true，如果其中一个为空，另一个不为空，或者两个都不为空，但是不相等，则返回false。</p>
<p>代码：</p>
<pre><code>bool isSameTree(TreeNode* p, TreeNode* q) {
    if (p == NULL &amp;&amp; q == NULL)
        return true;
    if ( (p != NULL &amp;&amp;  q == NULL) || (p == NULL &amp;&amp;  q != NULL) || ((p != NULL &amp;&amp; q != NULL) &amp;&amp; (p-&gt;val != q-&gt;val)) )
        return false;
    return isSameTree(p-&gt;left, q-&gt;left) &amp;&amp; isSameTree(p-&gt;right, q-&gt;right);

}
</code></pre><p>简单版：</p>
<pre><code>bool isSameTree(TreeNode* p, TreeNode* q) {
    if (p == NULL &amp;&amp; q == NULL)
        return true;
    if ((p != NULL &amp;&amp; q != NULL) &amp;&amp; (p-&gt;val == q-&gt;val)) 
        return isSameTree(p-&gt;left, q-&gt;left) &amp;&amp; isSameTree(p-&gt;right, q-&gt;right);
    else
        return false;
}
</code></pre><h3 id="101-对称二叉树"><a href="#101-对称二叉树" class="headerlink" title="101 对称二叉树"></a>101 对称二叉树</h3><p>给定一个二叉树，检查它是否是镜像对称的。</p>
<p>例如，二叉树 [1,2,2,3,4,4,3] 是对称的。</p>
<pre><code>    1
   / \
  2   2
 / \ / \
3  4 4  3
</code></pre><p>但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:</p>
<pre><code>  1
 / \
2   2
 \   \
 3    3
</code></pre><p>说明:</p>
<p>如果你可以运用递归和迭代两种方法解决这个问题，会很加分。</p>
<p>思路：递归的子问题是：判断两个子树中，一个子树的左子树是否等于另一个子树的右子树，一个子树的右子树是否等于另一个子树的左子树。</p>
<p>代码：</p>
<pre><code> bool isSymmetric(TreeNode* root) {
if (root == NULL)
        return true;
    return isSameTree(root-&gt;left, root-&gt;right);
}

bool isSameTree(TreeNode * p, TreeNode * q)
{
    if (p == NULL &amp;&amp; q == NULL)
        return true;
    if (p != NULL &amp;&amp; q != NULL &amp;&amp; p-&gt;val == q-&gt;val)
        return isSameTree(p-&gt;left, q-&gt;right) &amp;&amp; isSameTree(p-&gt;right, q-&gt;left);
    else
        return false;
}
</code></pre><h3 id="104-二叉树的最大深度"><a href="#104-二叉树的最大深度" class="headerlink" title="104. 二叉树的最大深度"></a>104. 二叉树的最大深度</h3><p>给定一个二叉树，找出其最大深度。</p>
<p>二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。</p>
<p>说明: 叶子节点是指没有子节点的节点。</p>
<p>示例：</p>
<p>给定二叉树 [3,9,20,null,null,15,7]，</p>
<pre><code>  3
 / \
9  20
  /  \
 15   7
</code></pre><p>返回它的最大深度 3 。</p>
<p>思路：递归</p>
<p>代码：</p>
<pre><code>int maxDepth(TreeNode* root) {
    if (root == NULL)
        return 0;
    return max(maxDepth(root-&gt;left), maxDepth(root-&gt;right))+1;
}
</code></pre><h3 id="107-二叉树的层次遍历-II"><a href="#107-二叉树的层次遍历-II" class="headerlink" title="107. 二叉树的层次遍历 II"></a>107. 二叉树的层次遍历 II</h3><p>给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）</p>
<p>例如：<br>给定二叉树 [3,9,20,null,null,15,7],</p>
<pre><code>  3
 / \
9  20
  /  \
 15   7
</code></pre><p>返回其自底向上的层次遍历为：</p>
<pre><code>[
  [15,7],
  [9,20],
  [3]
]
</code></pre><p>思路：通过队列实现。首先将根节点放入队列中。求出队列的长度，将队列中的元素放入一个数组中，当作一层的输出，并将队列中结点的子节点放入队列中，将上一层的节点在队列中删除。每一层的节点组成的数组放入一个新的数组中。</p>
<p>代码：</p>
<pre><code>vector&lt;vector&lt;int&gt;&gt; levelOrderBottom(TreeNode* root) {
    vector&lt;vector&lt;int&gt;&gt; res;
    if (root == NULL)
        return res;
    queue&lt;TreeNode*&gt; q;
    q.push(root); //将头节点放入队列中
    while (!q.empty())
    {
        int len = q.size(); //获取队列的长度
        vector&lt;int&gt; temp; 
        for (int i = 0; i &lt; len; i++) //将当前队列中的节点的值取出放入数组，并将节点的子树放入依次放入队列中
        {
            temp.push_back(q.front()-&gt;val); 
            if (q.front()-&gt;left != NULL)
                q.push(q.front()-&gt;left);
            if (q.front()-&gt;right != NULL)
                q.push(q.front()-&gt;right);
            q.pop();
        }
        res.insert(res.begin(), temp); //将一层节点的值放入结果数组中
    }
    return res;
}
</code></pre><h3 id="108-将有序数组转换为二叉搜索树"><a href="#108-将有序数组转换为二叉搜索树" class="headerlink" title="108. 将有序数组转换为二叉搜索树"></a>108. 将有序数组转换为二叉搜索树</h3><p>将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。</p>
<p>本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。</p>
<p>示例:</p>
<p>给定有序数组: [-10,-3,0,5,9],</p>
<p>一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：</p>
<pre><code>     0
    / \
  -3   9
  /   /
-10  5
</code></pre><p>思路： 递归的思想。每次将数组的中间元素作为根结点，左侧的元素位于左子树，右侧的元素位于右子树。</p>
<p>代码：</p>
<pre><code>TreeNode* sortedArrayToBST(vector&lt;int&gt;&amp; nums) {
    return sortedArrayToBST(nums, 0, nums.size()-1);
}
TreeNode * sortedArrayToBST(vector&lt;int&gt; &amp; nums, int i, int j)
{
    if (i &gt; j)
        return NULL;
    int mid = (j-i)/2+i;
    TreeNode * root = new TreeNode(nums[mid]);
    root-&gt;left = sortedArrayToBST(nums, i, mid-1);
    root-&gt;right = sortedArrayToBST(nums, mid+1, j);
    return root;
}
</code></pre><h3 id="110-平衡二叉树"><a href="#110-平衡二叉树" class="headerlink" title="110. 平衡二叉树"></a>110. 平衡二叉树</h3><p>给定一个二叉树，判断它是否是高度平衡的二叉树。</p>
<p>本题中，一棵高度平衡二叉树定义为：</p>
<p>一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。</p>
<p>示例 1:</p>
<p>给定二叉树 [3,9,20,null,null,15,7]</p>
<pre><code>  3
 / \
9  20
  /  \
 15   7
</code></pre><p>返回 true 。</p>
<p>示例 2:</p>
<p>给定二叉树 [1,2,2,3,3,null,null,4,4]</p>
<pre><code>      1
     / \
    2   2
   / \
  3   3
 / \
4   4
</code></pre><p>返回 false 。</p>
<p>思路： 首先判断树是否为空，或者树是否有子树，如果数为空，或者根节点没有子树，就返回true。否则，计算两棵子树的高度差，如果高度差小于1，则递归计算左右两棵子树是否满足平衡二叉树，否则直接返回false。</p>
<p>树的深度计算也是通过递归实现。</p>
<p>代码：</p>
<pre><code>bool isBalanced(TreeNode* root) {
    if (root == NULL || root-&gt;left == NULL &amp;&amp; root-&gt;right == NULL)
        return true;
    int t = abs(deepOfTree(root-&gt;left) - deepOfTree(root-&gt;right));
    if (t &lt;= 1)
        return isBalanced(root-&gt;left) &amp;&amp; isBalanced(root-&gt;right);
    else
        return false;

}
int deepOfTree(TreeNode * root)
{
    if (root == NULL)
        return 0;
    return max(deepOfTree(root-&gt;left), deepOfTree(root-&gt;right)) + 1;
}
</code></pre><p>上一种方法比较慢，使用了两次递归。下面的方法每次计算递归计算树的高度。</p>
<p>   bool isBalanced(TreeNode* root) {<br>        int h;<br>        return isBalanced(root, h);<br>    }</p>
<pre><code>bool isBalanced(TreeNode* root, int&amp; height) {
    if (root == nullptr)
    {
        height = 0;
        return true;
    }
    int h1, h2;
    bool flag = isBalanced(root-&gt;left, h1) &amp;&amp;
        isBalanced(root-&gt;right, h2);
    height = max(h1, h2) + 1;
    return flag &amp;&amp; abs(h1 - h2) &lt;= 1;
}
</code></pre><h3 id="111-二叉树的最小深度"><a href="#111-二叉树的最小深度" class="headerlink" title="111. 二叉树的最小深度"></a>111. 二叉树的最小深度</h3><p>给定一个二叉树，找出其最小深度。</p>
<p>最小深度是从根节点到最近叶子节点的最短路径上的节点数量。</p>
<p>说明: 叶子节点是指没有子节点的节点。</p>
<p>示例:</p>
<p>给定二叉树 [3,9,20,null,null,15,7],</p>
<pre><code>  3
 / \
9  20
  /  \
 15   7
</code></pre><p>返回它的最小深度  2.</p>
<p>思路：递归实现。每次取两颗子树的最小深度加1，终止条件根节点为NULL。</p>
<p>注意两种情况：一种根节点没有左子树，另一种是根节点没有右子树。即下面两种情况。</p>
<p><img src="https://i.imgur.com/C3QPVWZ.png" alt=""></p>
<p>上面两种情况，最小深度为3。需要单独考虑，如果不单独考虑，这两种情况的最小深度都为1。</p>
<p>代码：</p>
<pre><code>int minDepth(TreeNode* root) {
    if (root == NULL)
        return 0;
    if (root-&gt;left == NULL &amp;&amp; root-&gt;right != NULL)
        return minDepth(root-&gt;right)+1;
    if (root-&gt;left != NULL &amp;&amp; root-&gt;right == NULL)
        return minDepth(root-&gt;left)+1;
    return min(minDepth(root-&gt;left), minDepth(root-&gt;right)) + 1;
}
</code></pre><h3 id="112-路径总和"><a href="#112-路径总和" class="headerlink" title="112. 路径总和"></a>112. 路径总和</h3><p>给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。</p>
<p>说明: 叶子节点是指没有子节点的节点。</p>
<p>示例:<br>给定如下二叉树，以及目标和 sum = 22，</p>
<pre><code>      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1
</code></pre><p>返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5-&gt;4-&gt;11-&gt;2。</p>
<p>思路：递归思路。每次递归都减去当前节点的值，然后取两个子树递归结果的或。如果该节点为叶子节点并且sum=0，则返回true。如果当前节点为空节点返回false。</p>
<p>代码：</p>
<pre><code>bool hasPathSum(TreeNode* root, int sum) {
    if (root == NULL)
        return false;
    sum -= root-&gt;val;
    if (root-&gt;left == NULL &amp;&amp; root-&gt;right == NULL)
        return (sum == 0);
    return hasPathSum(root-&gt;left, sum) || hasPathSum(root-&gt;right, sum);
}
</code></pre><h3 id="226-翻转二叉树"><a href="#226-翻转二叉树" class="headerlink" title="226. 翻转二叉树"></a>226. 翻转二叉树</h3><p>翻转一棵二叉树。</p>
<p>示例：</p>
<p>输入：</p>
<pre><code>     4
   /   \
  2     7
 / \   / \
1   3 6   9
</code></pre><p>输出：</p>
<pre><code>     4
   /   \
  7     2
 / \   / \
9   6 3   1
</code></pre><p>备注:<br>这个问题是受到 Max Howell 的 原问题 启发的 ：</p>
<p>谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。</p>
<p>思路：先序遍历实现。</p>
<p>代码：</p>
<pre><code>TreeNode* invertTree(TreeNode* root) {
    if (root == NULL)
        return nullptr;
    TreeNode * temp = root-&gt;right;
    root-&gt;right = invertTree(root-&gt;left);
    root-&gt;left = invertTree(temp);
    return root;
}
</code></pre><p>其他方法：中序遍历和后序遍历实现跟先序遍历相似。还有一种就是层次遍历，利用队列实现。</p>
<p>代码：</p>
<pre><code>TreeNode* invertTree(TreeNode* root) {   
 //层次遍历实现
    if (root == NULL)
        return nullptr;
    queue&lt;TreeNode *&gt; q;
    q.push(root);
    while (!q.empty())
    {
        TreeNode * node = q.front();
        q.pop();
        TreeNode * temp = node-&gt;left;
        node-&gt;left = node-&gt;right;
        node-&gt;right = temp;
        if (node-&gt;left != NULL)
            q.push(node-&gt;left);
        if (node-&gt;right != NULL)
           q.push(node-&gt;right) ;
    }
    return root;
}
</code></pre><p>中序遍历和后序遍历理解有点困难：</p>
<pre><code>利用中序遍历
class Solution {
    public TreeNode invertTree(TreeNode root) {
            if (root == null) return null;
            invertTree(root.left); // 递归找到左节点
            TreeNode rightNode= root.right; // 保存右节点
            root.right = root.left;
            root.left = rightNode;
            // 递归找到右节点 继续交换 : 因为此时左右节点已经交换了,所以此时的右节点为root.left
            invertTree(root.left); 
    }
}

利用后序遍历
 class Solution {
        public TreeNode invertTree(TreeNode root) {
            // 后序遍历-- 从下向上交换
            if (root == null) return null;
            TreeNode leftNode = invertTree(root.left);
            TreeNode rightNode = invertTree(root.right);
            root.right = leftNode;
            root.left = rightNode;
            return root;
        }
    }
</code></pre><h3 id="235-二叉搜索树的最近公共祖先"><a href="#235-二叉搜索树的最近公共祖先" class="headerlink" title="235 二叉搜索树的最近公共祖先"></a>235 二叉搜索树的最近公共祖先</h3><p>给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。</p>
<p>百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”</p>
<p>例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]</p>
<p><img src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/binarysearchtree_improved.png" alt=""></p>
<p>示例 1:</p>
<pre><code>输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。
</code></pre><p>示例 2:</p>
<pre><code>输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
</code></pre><p>说明:</p>
<ul>
<li>所有节点的值都是唯一的。</li>
<li>p、q 为不同节点且均存在于给定的二叉搜索树中。</li>
</ul>
<p>来源：力扣（LeetCode）<br>链接：<a href="https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree" target="_blank" rel="noopener">https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree</a><br>著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。</p>
<p>思路： 利用二叉搜索树的特性，左子树的值小于根节点的值，右子树的值大于根节点的值。两个节点的最近祖先，满足该节点的值大于一个子节点的值，而小于另一个子节点的值。如果同时大于两个子节点，则表示两个子节点在节点的左子树上；如果同时小于两个子节点，则表示两个子节点在节点的右子树上。</p>
<p>代码：</p>
<pre><code>TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == NULL)
        return NULL;
    while (true)
    {
        if (root-&gt;val &gt; p-&gt;val &amp;&amp; root-&gt;val &gt; q-&gt;val)
            root = root-&gt;left;
        else if (root-&gt;val &lt; p-&gt;val &amp;&amp; root-&gt;val &lt; q-&gt;val)
            root = root-&gt;right;
        else
            return root;
    }
}
</code></pre><h3 id="257-二叉树的所有路径"><a href="#257-二叉树的所有路径" class="headerlink" title="257 二叉树的所有路径"></a>257 二叉树的所有路径</h3><p>给定一个二叉树，返回所有从根节点到叶子节点的路径。</p>
<p>说明: 叶子节点是指没有子节点的节点。</p>
<p>示例:</p>
<p>输入:</p>
<pre><code>   1
 /   \
2     3
 \
  5
</code></pre><p>输出: [“1-&gt;2-&gt;5”, “1-&gt;3”]</p>
<p>解释: 所有根节点到叶子节点的路径为: 1-&gt;2-&gt;5, 1-&gt;3</p>
<p>思路：递归方法，每次递归中都将结果利用引用的形式存放在参数中，而且将一个路径上的字符串也放在参数中，如果到达叶子节点则将字符串放入结果中。</p>
<p>代码：</p>
<pre><code>vector&lt;string&gt; binaryTreePaths(TreeNode* root) {
    vector&lt;string&gt; res;
    if (root == NULL)
        return res;
    string temp = &quot;&quot;;
    binaryTreePaths(root, temp, res);
    return res;

}
void binaryTreePaths(TreeNode * root, string temp, vector&lt;string&gt; &amp;res)
{
    if (root == NULL)
        return;
    temp += to_string(root-&gt;val);
    if (root-&gt;left == NULL &amp;&amp; root-&gt;right == NULL)
        res.push_back(temp);
    binaryTreePaths(root-&gt;left, temp + &quot;-&gt;&quot;, res);
    binaryTreePaths(root-&gt;right, temp + &quot;-&gt;&quot;, res);
}
</code></pre><h3 id="404-左叶子之和"><a href="#404-左叶子之和" class="headerlink" title="404 左叶子之和"></a>404 左叶子之和</h3><p>计算给定二叉树的所有左叶子之和。</p>
<p>示例：</p>
<pre><code>  3
 / \
9  20
  /  \
 15   7
</code></pre><p>在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24</p>
<p>思路：递归实现，递归函数中保护所要计算的结果和一个标记，标记用来标记一个节点是否为左节点。如果一个节点的左子树和右子树为空，并且标记为true(即为左子树)，则将该节点的值加入到结果中。</p>
<p>代码：</p>
<pre><code>int sumOfLeftLeaves(TreeNode* root) {
    if (root == NULL)
        return 0;
    int sum = 0;
    sumOfLeftLeaves(root, false, sum);
    return sum;
}
void sumOfLeftLeaves(TreeNode* root, bool flag, int &amp;sum) {
    if (root-&gt;left == NULL &amp;&amp; root-&gt;right == NULL &amp;&amp; flag == true)
    {
        sum += root-&gt;val;
        return;
    }
    if (root-&gt;left == NULL &amp;&amp; root-&gt;right == NULL &amp;&amp; flag == false)
        return;
    if (root-&gt;left != NULL)
        sumOfLeftLeaves(root-&gt;left, true, sum);
    if (root-&gt;right != NULL)
        sumOfLeftLeaves(root-&gt;right, false, sum);
}
</code></pre><p>另一种解法：</p>
<pre><code>int sumOfLeftLeaves(TreeNode* root) {
    int res = 0;
    if (root == nullptr)
        return res;
    if (root-&gt;left == nullptr &amp;&amp; root-&gt;right == nullptr)
        return res;
    if (root-&gt;left != nullptr &amp;&amp; root-&gt;left-&gt;left == nullptr &amp;&amp; root-&gt;left-&gt;right == nullptr)
        res += root-&gt;left-&gt;val;
    else if (root-&gt;left)
        res += sumOfLeftLeaves(root-&gt;left);
    if (root-&gt;right)
        res += sumOfLeftLeaves(root-&gt;right);
    return res;
}
</code></pre><h3 id="437-路径总和-Ⅲ"><a href="#437-路径总和-Ⅲ" class="headerlink" title="437 路径总和 Ⅲ"></a>437 路径总和 Ⅲ</h3><p>给定一个二叉树，它的每个结点都存放着一个整数值。</p>
<p>找出路径和等于给定数值的路径总数。</p>
<p>路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。</p>
<p>二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。</p>
<p>示例：</p>
<p>root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8</p>
<pre><code>      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1
</code></pre><p>返回 3。和等于 8 的路径有:</p>
<ol>
<li>5 -&gt; 3</li>
<li>5 -&gt; 2 -&gt; 1</li>
<li>-3 -&gt; 11</li>
</ol>
<p>思路：递归。利用数组来记录走过的路径。并判断当前路径是否等于sum。</p>
<p>代码：</p>
<pre><code>int pathSum(TreeNode* root, int sum) {
    if(root == nullptr) return 0;
    vector&lt;int&gt; buf;
    int res =0;
    pathSum_core(root,sum,buf,res);
    return res;
}

void pathSum_core(TreeNode *root,int sum,vector&lt;int&gt; &amp;buf, int &amp;res){
    if(root == nullptr) return;
    buf.push_back(root-&gt;val);
    int ans = 0;
    for(int i = buf.size()-1;i&gt;=0;i--){  
        ans += buf[i];
        if(ans == sum) res++;
    }
    pathSum_core(root-&gt;left,sum,buf,res);
    pathSum_core(root-&gt;right,sum,buf,res);
    buf.pop_back();
}
</code></pre><p>另一种方法比较笨，直接计算所有可能的路径，判断是否等于sum。效率比较低。</p>
<pre><code>int pathSum(TreeNode* root, int sum) {
    if (root == nullptr)
        return 0;
    return pathSum(root-&gt;left, sum) + pathSum(root-&gt;right, sum) + dfs(root, sum);
}
int dfs(TreeNode * root, int sum)
{
    if (root == nullptr)
        return 0;
    int count = 0;
    if (root-&gt;val == sum)
        count += 1;

    return count + dfs(root-&gt;left, sum - root-&gt;val) + dfs(root-&gt;right, sum - root-&gt;val);
}
</code></pre>
      
    </div>
    
    
    

    
      <div>
        <div id="wechat_subscriber" style="display: block; padding: 10px 0; margin: 20px auto; width: 100%; text-align: center">
    <img id="wechat_subscriber_qcode" src="/images/wechat-qcode.jpg" alt="zxp wechat" style="width: 200px; max-width: 100%;"/>
    <div>欢迎关注微信公众号！</div>
</div>

      </div>
    

    
      <div>
        <div style="padding: 10px 0; margin: 20px auto; width: 90%; text-align: center;">
  <div></div>
  <button id="rewardButton" disable="enable" onclick="var qr = document.getElementById('QR'); if (qr.style.display === 'none') {qr.style.display='block';} else {qr.style.display='none'}">
    <span>打赏</span>
  </button>
  <div id="QR" style="display: none;">

    
      <div id="wechat" style="display: inline-block">
        <img id="wechat_qr" src="/images/WeChatpay.jpg" alt="zxp 微信支付"/>
        <p>微信支付</p>
      </div>
    

    
      <div id="alipay" style="display: inline-block">
        <img id="alipay_qr" src="/images/Alipay.jpg" alt="zxp 支付宝"/>
        <p>支付宝</p>
      </div>
    

    

  </div>
</div>

      </div>
    

    
      <div>
        <ul class="post-copyright">
  <li class="post-copyright-author">
    <strong>本文作者：</strong>
    zxp
  </li>
  <li class="post-copyright-link">
    <strong>本文链接：</strong>
    <a href="https://zxpgo.github.io/2019/06/22/LeetCode算法题目C++/" title="LeetCode算法题目C++">https://zxpgo.github.io/2019/06/22/LeetCode算法题目C++/</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>
    本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/3.0/" rel="external nofollow" target="_blank">CC BY-NC-SA 3.0</a> 许可协议。转载请注明出处！
  </li>
</ul>

      </div>
    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tag/面试题目/" rel="tag"># 面试题目</a>
          
        </div>
      

      
      
        <div class="post-widgets">
        

        

        
          
          <div id="needsharebutton-postbottom">
            <span class="btn">
              <i class="fa fa-share-alt" aria-hidden="true"></i>
            </span>
          </div>
        
        </div>
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2019/06/22/滑动窗口/" rel="next" title="滑动窗口解决子串问题(LeetCode)">
                <i class="fa fa-chevron-left"></i> 滑动窗口解决子串问题(LeetCode)
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2019/07/08/QT/" rel="prev" title="QT教程">
                QT教程 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          

  
    <div class="comments" id="comments">
      <div id="lv-container" data-id="city" data-uid="MTAyMC8zODgxNC8xNTM0Mg=="></div>
    </div>

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image"
                src="/images/avatar.gif"
                alt="zxp" />
            
              <p class="site-author-name" itemprop="name">zxp</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">176</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">16</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">48</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          
            <div class="feed-link motion-element">
              <a href="/atom.xml" rel="alternate">
                <i class="fa fa-rss"></i>
                RSS
              </a>
            </div>
          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a href="https://blog.csdn.net/qq_25774883" target="_blank" title="CSDN">
                      
                        <i class="fa fa-fw fa-globe"></i>CSDN</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="https://github.com/zxpgo/zxpgo" target="_blank" title="GitHub">
                      
                        <i class="fa fa-fw fa-globe"></i>GitHub</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="https://www.linkedin.com/feed/" target="_blank" title="LinkedIn">
                      
                        <i class="fa fa-fw fa-globe"></i>LinkedIn</a>
                  </span>
                
                  <span class="links-of-author-item">
                    <a href="1165772354@qq.com" target="_blank" title="E-Mail">
                      
                        <i class="fa fa-fw fa-envelope"></i>E-Mail</a>
                  </span>
                
            </div>
          

          
          

          
          
            <div class="links-of-blogroll motion-element links-of-blogroll-inline">
              <div class="links-of-blogroll-title">
                <i class="fa  fa-fw fa-link"></i>
                友情链接
              </div>
              <ul class="links-of-blogroll-list">
                
                  <li class="links-of-blogroll-item">
                    <a href="http://theme-next.iissnan.com" title="Next主题" target="_blank">Next主题</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="http://blog.rexking6.top" title="青爷博客" target="_blank">青爷博客</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://me.csdn.net/download/qq_25774883" title="CSDN下载" target="_blank">CSDN下载</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://www.livere.com/" title="来必力" target="_blank">来必力</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://tongji.baidu.com/web/welcome/login" title="百度统计" target="_blank">百度统计</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://leancloud.cn/" title="LeanCloud" target="_blank">LeanCloud</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="http://ibruce.info/2015/04/04/busuanzi/" title="不蒜子" target="_blank">不蒜子</a>
                  </li>
                
                  <li class="links-of-blogroll-item">
                    <a href="https://leetcode-cn.com/" title="LeetCode" target="_blank">LeetCode</a>
                  </li>
                
              </ul>
            </div>
          

          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-3"><a class="nav-link" href="#7-整数反转"><span class="nav-number">1.</span> <span class="nav-text">7. 整数反转</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#9-回文数"><span class="nav-number">2.</span> <span class="nav-text">9. 回文数</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#13-罗马数字转整数"><span class="nav-number">3.</span> <span class="nav-text">13. 罗马数字转整数</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#14-最长公共前缀"><span class="nav-number">4.</span> <span class="nav-text">14. 最长公共前缀</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#20-有效的括号"><span class="nav-number">5.</span> <span class="nav-text">20. 有效的括号</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#28-实现strStr"><span class="nav-number">6.</span> <span class="nav-text">28. 实现strStr()</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#38-报数"><span class="nav-number">7.</span> <span class="nav-text">38. 报数</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#53-最大子序和"><span class="nav-number">8.</span> <span class="nav-text">53. 最大子序和</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#58-最后一个单词的长度"><span class="nav-number">9.</span> <span class="nav-text">58. 最后一个单词的长度</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#66-加一"><span class="nav-number">10.</span> <span class="nav-text">66. 加一</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#67-二进制求和"><span class="nav-number">11.</span> <span class="nav-text">67. 二进制求和</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#第二周"><span class="nav-number"></span> <span class="nav-text">第二周</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#69-x的平方根"><span class="nav-number">1.</span> <span class="nav-text">69. x的平方根</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#83-删除排序列表中的重复元素"><span class="nav-number">2.</span> <span class="nav-text">83. 删除排序列表中的重复元素</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#88-合并两个有序数组"><span class="nav-number">3.</span> <span class="nav-text">88. 合并两个有序数组</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#1-两数之和"><span class="nav-number">4.</span> <span class="nav-text">1. 两数之和</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#26-删除排序数组中的重复项"><span class="nav-number">5.</span> <span class="nav-text">26. 删除排序数组中的重复项</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#27-移除重复元素"><span class="nav-number">6.</span> <span class="nav-text">27. 移除重复元素</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#35-搜索插入位置"><span class="nav-number">7.</span> <span class="nav-text">35. 搜索插入位置</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#118-杨辉三角"><span class="nav-number">8.</span> <span class="nav-text">118. 杨辉三角</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#119-杨辉三角Ⅱ"><span class="nav-number">9.</span> <span class="nav-text">119. 杨辉三角Ⅱ</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#121-买卖股票的最佳时机-Ⅰ"><span class="nav-number">10.</span> <span class="nav-text">121. 买卖股票的最佳时机 Ⅰ</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#122-买卖股票的最佳时机Ⅱ"><span class="nav-number">11.</span> <span class="nav-text">122. 买卖股票的最佳时机Ⅱ</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#167-两数之和Ⅱ-输入有序数组"><span class="nav-number">12.</span> <span class="nav-text">167. 两数之和Ⅱ-输入有序数组</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#169-求众数"><span class="nav-number">13.</span> <span class="nav-text">169. 求众数</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#189-旋转数组"><span class="nav-number">14.</span> <span class="nav-text">189. 旋转数组</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#217-存在重复元素"><span class="nav-number">15.</span> <span class="nav-text">217. 存在重复元素</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#219-存在重复元素Ⅱ"><span class="nav-number">16.</span> <span class="nav-text">219. 存在重复元素Ⅱ</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#268-缺失数字"><span class="nav-number">17.</span> <span class="nav-text">268. 缺失数字</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#283-移动零"><span class="nav-number">18.</span> <span class="nav-text">283. 移动零</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#414-第三大的数"><span class="nav-number">19.</span> <span class="nav-text">414. 第三大的数</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#448-找到所有数组中消失的数字"><span class="nav-number">20.</span> <span class="nav-text">448. 找到所有数组中消失的数字</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#485-最大连续的个数"><span class="nav-number">21.</span> <span class="nav-text">485. 最大连续的个数</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#532-数组中的K-diff数对"><span class="nav-number">22.</span> <span class="nav-text">532. 数组中的K-diff数对</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#561-数组拆分Ⅰ"><span class="nav-number">23.</span> <span class="nav-text">561. 数组拆分Ⅰ</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#566-重塑矩阵"><span class="nav-number">24.</span> <span class="nav-text">566. 重塑矩阵</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#581-最短无序连续子数组"><span class="nav-number">25.</span> <span class="nav-text">581. 最短无序连续子数组</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#605-种花问题"><span class="nav-number">26.</span> <span class="nav-text">605. 种花问题</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#628-三个数的最大乘积"><span class="nav-number">27.</span> <span class="nav-text">628. 三个数的最大乘积</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#643-子数组最大平均数-I"><span class="nav-number">28.</span> <span class="nav-text">643 子数组最大平均数 I</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#661-图片平滑器"><span class="nav-number">29.</span> <span class="nav-text">661. 图片平滑器</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#665-非递减数列"><span class="nav-number">30.</span> <span class="nav-text">665. 非递减数列</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#746-使用最小花费爬楼梯"><span class="nav-number">31.</span> <span class="nav-text">746. 使用最小花费爬楼梯</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#动态规划"><span class="nav-number"></span> <span class="nav-text">动态规划</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#5-最大子序和"><span class="nav-number">1.</span> <span class="nav-text">5. 最大子序和</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#70-爬楼梯"><span class="nav-number">2.</span> <span class="nav-text">70 爬楼梯</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#121-买卖股票的最佳时机"><span class="nav-number">3.</span> <span class="nav-text">121 买卖股票的最佳时机</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#198-打家劫舍"><span class="nav-number">4.</span> <span class="nav-text">198 打家劫舍</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#213-打家劫舍-Ⅱ（中等）"><span class="nav-number">5.</span> <span class="nav-text">213 打家劫舍 Ⅱ（中等）</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#303-区域和检索-数组不可变"><span class="nav-number">6.</span> <span class="nav-text">303  区域和检索 - 数组不可变</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#746-使用最小花费爬楼梯-1"><span class="nav-number">7.</span> <span class="nav-text">746 使用最小花费爬楼梯</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#1025-除数博弈"><span class="nav-number">7.1.</span> <span class="nav-text">1025. 除数博弈</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#字符串"><span class="nav-number"></span> <span class="nav-text">字符串</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#415-字符串相加"><span class="nav-number">1.</span> <span class="nav-text">415 字符串相加</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#434-字符串中的单词数"><span class="nav-number">2.</span> <span class="nav-text">434 字符串中的单词数</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#443-压缩字符串"><span class="nav-number">3.</span> <span class="nav-text">443 压缩字符串</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#459-重复得子字符串"><span class="nav-number">4.</span> <span class="nav-text">459 重复得子字符串</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#520-检测大写字母"><span class="nav-number">5.</span> <span class="nav-text">520. 检测大写字母</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#521-最长特殊序列-Ⅰ"><span class="nav-number">6.</span> <span class="nav-text">521 最长特殊序列 Ⅰ</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#541-反转字符串-II"><span class="nav-number">7.</span> <span class="nav-text">541 反转字符串 II</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#551-学生出勤记录"><span class="nav-number">8.</span> <span class="nav-text">551 学生出勤记录</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#树"><span class="nav-number"></span> <span class="nav-text">树</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#100-相同的树"><span class="nav-number">1.</span> <span class="nav-text">100 相同的树</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#101-对称二叉树"><span class="nav-number">2.</span> <span class="nav-text">101 对称二叉树</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#104-二叉树的最大深度"><span class="nav-number">3.</span> <span class="nav-text">104. 二叉树的最大深度</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#107-二叉树的层次遍历-II"><span class="nav-number">4.</span> <span class="nav-text">107. 二叉树的层次遍历 II</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#108-将有序数组转换为二叉搜索树"><span class="nav-number">5.</span> <span class="nav-text">108. 将有序数组转换为二叉搜索树</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#110-平衡二叉树"><span class="nav-number">6.</span> <span class="nav-text">110. 平衡二叉树</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#111-二叉树的最小深度"><span class="nav-number">7.</span> <span class="nav-text">111. 二叉树的最小深度</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#112-路径总和"><span class="nav-number">8.</span> <span class="nav-text">112. 路径总和</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#226-翻转二叉树"><span class="nav-number">9.</span> <span class="nav-text">226. 翻转二叉树</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#235-二叉搜索树的最近公共祖先"><span class="nav-number">10.</span> <span class="nav-text">235 二叉搜索树的最近公共祖先</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#257-二叉树的所有路径"><span class="nav-number">11.</span> <span class="nav-text">257 二叉树的所有路径</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#404-左叶子之和"><span class="nav-number">12.</span> <span class="nav-text">404 左叶子之和</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#437-路径总和-Ⅲ"><span class="nav-number">13.</span> <span class="nav-text">437 路径总和 Ⅲ</span></a></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div>
<script async src="https//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
<i class="fa fa-user-md"></i><span id="busuanzi_container_site_pv" style='display:none'>
    本站总访问量 <span id="busuanzi_value_site_pv"></span> 
    <span class="post-meta-divider">|</span>
</span>
<span id="busuanzi_container_site_uv" style='display:none'>
    访问人数 <span id="busuanzi_value_site_uv"></span>
</span>
</div>


<script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>

<div class="copyright">&copy; 2018-8 &mdash; <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-"></i> Power by 
  </span>
  <span class="author" itemprop="copyrightHolder">zxp</span>
  
  
</div>









        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    
      <div id="needsharebutton-float">
        <span class="btn">
          <i class="fa fa-share-alt" aria-hidden="true"></i>
        </span>
      </div>
    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.4"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.4"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  




  
  <div id="lv-container" data-uid="MTAyMC8zODgxNC8xNTM0Mg==">
    <script type="text/javascript">
      (function(d, s) {
        var j, e = d.getElementsByTagName(s)[0];
        if (typeof LivereTower === 'function') { return; }
        j = d.createElement(s);
        j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
        j.async = true;
        e.parentNode.insertBefore(j, e);
      })(document, 'script');
    </script>
	</div>
  











  

  <script type="text/javascript">
    // Popup Window;
    var isfetched = false;
    var isXml = true;
    // Search DB path;
    var search_path = "search.xml";
    if (search_path.length === 0) {
      search_path = "search.xml";
    } else if (/json$/i.test(search_path)) {
      isXml = false;
    }
    var path = "/" + search_path;
    // monitor main search box;

    var onPopupClose = function (e) {
      $('.popup').hide();
      $('#local-search-input').val('');
      $('.search-result-list').remove();
      $('#no-result').remove();
      $(".local-search-pop-overlay").remove();
      $('body').css('overflow', '');
    }

    function proceedsearch() {
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
        .css('overflow', 'hidden');
      $('.search-popup-overlay').click(onPopupClose);
      $('.popup').toggle();
      var $localSearchInput = $('#local-search-input');
      $localSearchInput.attr("autocapitalize", "none");
      $localSearchInput.attr("autocorrect", "off");
      $localSearchInput.focus();
    }

    // search function;
    var searchFunc = function(path, search_id, content_id) {
      'use strict';

      // start loading animation
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay">' +
          '<div id="search-loading-icon">' +
          '<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
          '</div>' +
          '</div>')
        .css('overflow', 'hidden');
      $("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');

      $.ajax({
        url: path,
        dataType: isXml ? "xml" : "json",
        async: true,
        success: function(res) {
          // get the contents from search data
          isfetched = true;
          $('.popup').detach().appendTo('.header-inner');
          var datas = isXml ? $("entry", res).map(function() {
            return {
              title: $("title", this).text(),
              content: $("content",this).text(),
              url: $("url" , this).text()
            };
          }).get() : res;
          var input = document.getElementById(search_id);
          var resultContent = document.getElementById(content_id);
          var inputEventFunction = function() {
            var searchText = input.value.trim().toLowerCase();
            var keywords = searchText.split(/[\s\-]+/);
            if (keywords.length > 1) {
              keywords.push(searchText);
            }
            var resultItems = [];
            if (searchText.length > 0) {
              // perform local searching
              datas.forEach(function(data) {
                var isMatch = false;
                var hitCount = 0;
                var searchTextCount = 0;
                var title = data.title.trim();
                var titleInLowerCase = title.toLowerCase();
                var content = data.content.trim().replace(/<[^>]+>/g,"");
                var contentInLowerCase = content.toLowerCase();
                var articleUrl = decodeURIComponent(data.url);
                var indexOfTitle = [];
                var indexOfContent = [];
                // only match articles with not empty titles
                if(title != '') {
                  keywords.forEach(function(keyword) {
                    function getIndexByWord(word, text, caseSensitive) {
                      var wordLen = word.length;
                      if (wordLen === 0) {
                        return [];
                      }
                      var startPosition = 0, position = [], index = [];
                      if (!caseSensitive) {
                        text = text.toLowerCase();
                        word = word.toLowerCase();
                      }
                      while ((position = text.indexOf(word, startPosition)) > -1) {
                        index.push({position: position, word: word});
                        startPosition = position + wordLen;
                      }
                      return index;
                    }

                    indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
                    indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
                  });
                  if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
                    isMatch = true;
                    hitCount = indexOfTitle.length + indexOfContent.length;
                  }
                }

                // show search results

                if (isMatch) {
                  // sort index by position of keyword

                  [indexOfTitle, indexOfContent].forEach(function (index) {
                    index.sort(function (itemLeft, itemRight) {
                      if (itemRight.position !== itemLeft.position) {
                        return itemRight.position - itemLeft.position;
                      } else {
                        return itemLeft.word.length - itemRight.word.length;
                      }
                    });
                  });

                  // merge hits into slices

                  function mergeIntoSlice(text, start, end, index) {
                    var item = index[index.length - 1];
                    var position = item.position;
                    var word = item.word;
                    var hits = [];
                    var searchTextCountInSlice = 0;
                    while (position + word.length <= end && index.length != 0) {
                      if (word === searchText) {
                        searchTextCountInSlice++;
                      }
                      hits.push({position: position, length: word.length});
                      var wordEnd = position + word.length;

                      // move to next position of hit

                      index.pop();
                      while (index.length != 0) {
                        item = index[index.length - 1];
                        position = item.position;
                        word = item.word;
                        if (wordEnd > position) {
                          index.pop();
                        } else {
                          break;
                        }
                      }
                    }
                    searchTextCount += searchTextCountInSlice;
                    return {
                      hits: hits,
                      start: start,
                      end: end,
                      searchTextCount: searchTextCountInSlice
                    };
                  }

                  var slicesOfTitle = [];
                  if (indexOfTitle.length != 0) {
                    slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
                  }

                  var slicesOfContent = [];
                  while (indexOfContent.length != 0) {
                    var item = indexOfContent[indexOfContent.length - 1];
                    var position = item.position;
                    var word = item.word;
                    // cut out 100 characters
                    var start = position - 20;
                    var end = position + 80;
                    if(start < 0){
                      start = 0;
                    }
                    if (end < position + word.length) {
                      end = position + word.length;
                    }
                    if(end > content.length){
                      end = content.length;
                    }
                    slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
                  }

                  // sort slices in content by search text's count and hits' count

                  slicesOfContent.sort(function (sliceLeft, sliceRight) {
                    if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
                      return sliceRight.searchTextCount - sliceLeft.searchTextCount;
                    } else if (sliceLeft.hits.length !== sliceRight.hits.length) {
                      return sliceRight.hits.length - sliceLeft.hits.length;
                    } else {
                      return sliceLeft.start - sliceRight.start;
                    }
                  });

                  // select top N slices in content

                  var upperBound = parseInt('1');
                  if (upperBound >= 0) {
                    slicesOfContent = slicesOfContent.slice(0, upperBound);
                  }

                  // highlight title and content

                  function highlightKeyword(text, slice) {
                    var result = '';
                    var prevEnd = slice.start;
                    slice.hits.forEach(function (hit) {
                      result += text.substring(prevEnd, hit.position);
                      var end = hit.position + hit.length;
                      result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
                      prevEnd = end;
                    });
                    result += text.substring(prevEnd, slice.end);
                    return result;
                  }

                  var resultItem = '';

                  if (slicesOfTitle.length != 0) {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
                  } else {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
                  }

                  slicesOfContent.forEach(function (slice) {
                    resultItem += "<a href='" + articleUrl + "'>" +
                      "<p class=\"search-result\">" + highlightKeyword(content, slice) +
                      "...</p>" + "</a>";
                  });

                  resultItem += "</li>";
                  resultItems.push({
                    item: resultItem,
                    searchTextCount: searchTextCount,
                    hitCount: hitCount,
                    id: resultItems.length
                  });
                }
              })
            };
            if (keywords.length === 1 && keywords[0] === "") {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
            } else if (resultItems.length === 0) {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
            } else {
              resultItems.sort(function (resultLeft, resultRight) {
                if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
                  return resultRight.searchTextCount - resultLeft.searchTextCount;
                } else if (resultLeft.hitCount !== resultRight.hitCount) {
                  return resultRight.hitCount - resultLeft.hitCount;
                } else {
                  return resultRight.id - resultLeft.id;
                }
              });
              var searchResultList = '<ul class=\"search-result-list\">';
              resultItems.forEach(function (result) {
                searchResultList += result.item;
              })
              searchResultList += "</ul>";
              resultContent.innerHTML = searchResultList;
            }
          }

          if ('auto' === 'auto') {
            input.addEventListener('input', inputEventFunction);
          } else {
            $('.search-icon').click(inputEventFunction);
            input.addEventListener('keypress', function (event) {
              if (event.keyCode === 13) {
                inputEventFunction();
              }
            });
          }

          // remove loading animation
          $(".local-search-pop-overlay").remove();
          $('body').css('overflow', '');

          proceedsearch();
        }
      });
    }

    // handle and trigger popup window;
    $('.popup-trigger').click(function(e) {
      e.stopPropagation();
      if (isfetched === false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };
    });

    $('.popup-btn-close').click(onPopupClose);
    $('.popup').click(function(e){
      e.stopPropagation();
    });
    $(document).on('keyup', function (event) {
      var shouldDismissSearchPopup = event.which === 27 &&
        $('.search-popup').is(':visible');
      if (shouldDismissSearchPopup) {
        onPopupClose();
      }
    });
  </script>





  

  
  <script src="https://cdn1.lncld.net/static/js/av-core-mini-0.6.4.js"></script>
  <script>AV.initialize("2AyV3DKioBSdoryrFLRohzjB-gzGzoHsz", "XynedcHyJCVCrTfbD4yYnodo");</script>
  <script>
    function showTime(Counter) {
      var query = new AV.Query(Counter);
      var entries = [];
      var $visitors = $(".leancloud_visitors");

      $visitors.each(function () {
        entries.push( $(this).attr("id").trim() );
      });

      query.containedIn('url', entries);
      query.find()
        .done(function (results) {
          var COUNT_CONTAINER_REF = '.leancloud-visitors-count';

          if (results.length === 0) {
            $visitors.find(COUNT_CONTAINER_REF).text(0);
            return;
          }

          for (var i = 0; i < results.length; i++) {
            var item = results[i];
            var url = item.get('url');
            var time = item.get('time');
            var element = document.getElementById(url);

            $(element).find(COUNT_CONTAINER_REF).text(time);
          }
          for(var i = 0; i < entries.length; i++) {
            var url = entries[i];
            var element = document.getElementById(url);
            var countSpan = $(element).find(COUNT_CONTAINER_REF);
            if( countSpan.text() == '') {
              countSpan.text(0);
            }
          }
        })
        .fail(function (object, error) {
          console.log("Error: " + error.code + " " + error.message);
        });
    }

    function addCount(Counter) {
      var $visitors = $(".leancloud_visitors");
      var url = $visitors.attr('id').trim();
      var title = $visitors.attr('data-flag-title').trim();
      var query = new AV.Query(Counter);

      query.equalTo("url", url);
      query.find({
        success: function(results) {
          if (results.length > 0) {
            var counter = results[0];
            counter.fetchWhenSave(true);
            counter.increment("time");
            counter.save(null, {
              success: function(counter) {
                var $element = $(document.getElementById(url));
                $element.find('.leancloud-visitors-count').text(counter.get('time'));
              },
              error: function(counter, error) {
                console.log('Failed to save Visitor num, with error message: ' + error.message);
              }
            });
          } else {
            var newcounter = new Counter();
            /* Set ACL */
            var acl = new AV.ACL();
            acl.setPublicReadAccess(true);
            acl.setPublicWriteAccess(true);
            newcounter.setACL(acl);
            /* End Set ACL */
            newcounter.set("title", title);
            newcounter.set("url", url);
            newcounter.set("time", 1);
            newcounter.save(null, {
              success: function(newcounter) {
                var $element = $(document.getElementById(url));
                $element.find('.leancloud-visitors-count').text(newcounter.get('time'));
              },
              error: function(newcounter, error) {
                console.log('Failed to create');
              }
            });
          }
        },
        error: function(error) {
          console.log('Error:' + error.code + " " + error.message);
        }
      });
    }

    $(function() {
      var Counter = AV.Object.extend("Counter");
      if ($('.leancloud_visitors').length == 1) {
        addCount(Counter);
      } else if ($('.post-title-link').length > 1) {
        showTime(Counter);
      }
    });
  </script>



  

  
<script>
(function(){
    var bp = document.createElement('script');
    var curProtocol = window.location.protocol.split(':')[0];
    if (curProtocol === 'https') {
        bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';        
    }
    else {
        bp.src = 'http://push.zhanzhang.baidu.com/push.js';
    }
    var s = document.getElementsByTagName("script")[0];
    s.parentNode.insertBefore(bp, s);
})();
</script>


  
  
  
  <link rel="stylesheet" href="/lib/needsharebutton/needsharebutton.css">

  
  
  <script src="/lib/needsharebutton/needsharebutton.js"></script>

  <script>
    
      pbOptions = {};
      
          pbOptions.iconStyle = "default";
      
          pbOptions.boxForm = "vertical";
      
          pbOptions.position = "top";
      
          pbOptions.networks = "Weibo,Wechat,Douban,QQZone,Twitter,Facebook";
      
      new needShareButton('#needsharebutton-postbottom', pbOptions);
    
    
      flOptions = {};
      
          flOptions.iconStyle = "box";
      
          flOptions.boxForm = "horizontal";
      
          flOptions.position = "middleRight";
      
          flOptions.networks = "Weibo,Wechat,Douban,QQZone,Twitter,Facebook";
      
      new needShareButton('#needsharebutton-float', flOptions);
    
  </script>

  

  
  


  
  <script type="text/javascript" src="/js/src/js.cookie.js?v=5.1.4"></script>
  <script type="text/javascript" src="/js/src/scroll-cookie.js?v=5.1.4"></script>


  
  <script type="text/javascript" src="/js/src/exturl.js?v=5.1.4"></script>


  
  
  	 <!-- custom analytics part create by xiamo -->
<script src="https://cdn1.lncld.net/static/js/av-core-mini-0.6.1.js"></script>
<script>AV.initialize("2AyV3DKioBSdoryrFLRohzjB-gzGzoHsz", "XynedcHyJCVCrTfbD4yYnodo");</script>
<script>
function showTime(Counter) {
	var query = new AV.Query(Counter);
	$(".leancloud_visitors").each(function() {
		var url = $(this).attr("id").trim();
		query.equalTo("url", url);
		query.find({
			success: function(results) {
				if (results.length == 0) {
					var content = $(document.getElementById(url)).text() + ' 0';
					$(document.getElementById(url)).text(content);
					return;
				}
				for (var i = 0; i < results.length; i++) {
					var object = results[i];
					var content = $(document.getElementById(url)).text() + ' ' + object.get('time');
					$(document.getElementById(url)).text(content);
				}
			}
		});

	});
}

</script>
  
</body>
</html>
